All this time, I thought this was graphic designer dark-magic, and it turns out its mostly knowing how to use photoshop!
- Create a pattern in photoshop,
- Go to Filter -> Offset -> Set both sliders to 1/2 of your image size
- Use the Clone tool to fix the seam down the middle if it exists
Totally thanks to: http://designshack.net/articles/css/create-seamless-web-background-textures-in-minutes/