There has been a fair number of posts on creating seamless textures for use in maps, the largest one here.

Extending on that topic, here is a technique to create seamless texture sets, or multiple tiles that are all seamless with one another. I first read about the technique in the dundjinni forums, as that program supports tile randomization.

The original site is not available: http://www.vsf.cape.com/~jdale/dundjinni/tut_tiles.htm

but there is still a cache in the wayback machine: http://web.archive.org/web/200701082.../tut_tiles.htm

As I don't know how long that will be available, I will walk through the process here.

The Tutorial

I am starting with an image from CGTextures that I have scaled down:
2008-10-22_124446.jpg

I want 200x200 px tiles so I set the rectangular selection to be fixed 200x200:
2008-10-22_124524.jpg

And copy and paste a selection to a new image:
2008-10-22_124748.jpg

Which is made seamless using your preferred technique:
2008-10-22_124851.jpg

This will be the base image that all other tiles will be made from. Duplicate the layer and make a squiggly feathered selection in the middle:
2008-10-22_124950.jpg

Then...