I usually start out with a seamless pattern generated with a utility like this AWESOME free one:
neotextureedit.sourceforge.net
Very cool little product, there are comercial products like Genetica too that make seamless tiles.
I used Texturemaker for years now, but it does not seem to function with windows Vista or higher.
Once I have a seamless pattern I will import it into ink scape and Set my shape template to use the seamless pattern.
In the past I have done the same thing with Blender, but that is a lot more tricky if you are not accustomed to the blender GUI, and workflow.
The nice thing about blender is that you can do shaded things with normal maps, just make sure you set your camera to Ortho-scopic, and pit whatever kind of light that you choose behind you shing directly off a 90 degree angle from the tile face normal.
Inkscape and GIMP are the applications I turn to most in this situation.
I like Inkscape over GIMP because it is so easy to change a single color throughout the entire document.
The main thing about seamless texture is that you want to Homogenize the colors somewhat so there is no real noticeable feature that really stands out.
Texture maker actually has a Homogenize filter , not sure where to find it for Gimp or neo-texture edit.
Another nice tool is a macro-feature resampler. Gimp has one called Textureize, and Texturemaker had one called iSample.
texturemaker.com/tour.php
The Gimp plugin was linux only the last time I checked. I am sure there are others that re-synthesize a texture swatch.
I will use a "variator" decal that I will put over some of my tiles to break things up too. Just small alpha masked things, like patches of grass and rocks to go over a dirt texture. Or on top of a grass block, I will put things like an alpha masked patch of grass, some flowes, or little piles of rubble.
Hope you find some of this useful :)