Lots and lots of googling, ngl haha. Some things I find myself googling a lot for backgrounds:
Damask
Color names
Textured
I ALWAYS put "seamless" into whatever phrase I'm searching.
Like, I'll google "pink seamless background" or "seamless black texture" or "seamless damask," and if I can't find a color I like, I pick a pattern and fix it in GIMP.
If the pattern isn't too thin, what I like to do is add transparency, adjust contrast as needed to separate the bg from the pattern, delete the bg color, copy the pattern to a path, make a new layer and select to path, then paint over it in a low-medium opacity white or black. Then I can use it on ANY color bg, and then delete the original first layer and save it as a PNG.
Example: When I was commission for this layout that's exactly what I did for the floral. You can't see the second link at all, but stick it on any color background (that isn't too light) and you have a pattern in any color you want. :D
Oh, and uh... if you aren't graphically inclined and that all sounded like gibberish I can put up a tutorial if you want! ♥