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:
Click image for larger version. 

Name:	2008-10-22_124446.jpg 
Views:	125 
Size:	166.1 KB 
ID:	7265

I want 200x200 px tiles so I set the rectangular selection to be fixed 200x200:
Click image for larger version. 

Name:	2008-10-22_124524.jpg 
Views:	61 
Size:	52.2 KB 
ID:	7266

And copy and paste a selection to a new image:
Click image for larger version. 

Name:	2008-10-22_124748.jpg 
Views:	72 
Size:	193.5 KB 
ID:	7267

Which is made seamless using your preferred technique:
Click image for larger version. 

Name:	2008-10-22_124851.jpg 
Views:	70 
Size:	57.4 KB 
ID:	7268

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:
Click image for larger version. 

Name:	2008-10-22_124950.jpg 
Views:	61 
Size:	55.0 KB 
ID:	7269

Then...