From memory without testing (been a long time since I did one of these and I haven't got PS on this laptop):
Create your pattern as you see fit. Go filters>Other>offset. Adjust x and y to be 50% of your x and y dimensions (so if your image is 100x100 set to 50 for both).
Use the clone tool to get rid of the cross that will likely be overlapping the center of your image.
Offset again by a different amount and see if there is another area that will not tile perfectly. If so, rinse and repeat.
edit: The above applies to photoshop.
__________________