Since you're already using Photoshop by the sound of it, I think there's a feature built into Photoshop (I think it was added in version 7, if not in CS2) for making tiled backgrounds.
I haven't really played with it myself (if only I had the time to read through the whole PS manual and learn all the features!) so I don't know how well it will work. From a quick search through the help file it looks like the feature is called "The Pattern Maker filter", but it's possible I've found the wrong thing.
I get the impression it is somewhat automatic so it'll probably work well for certain things, like grass textures where you can safely blend parts together, but not for others where you need more structure to the repetition.
Something I miss way back from Deluxe Paint on the Amiga was the tiled painting mode where you'd define a tile size and then everything you did to the image was repeated in each tile. That was great for making repeating backgrounds since you could paint them directly without having to work out how the overlap would look. In Photoshop, unless there's something I don't know about, you'd have to pain the tile once, then offset it by 50% width and height and make the edges match up, then repeat if you messed up the other edges in the process, until done.