Vectorizing the Image
This is, by far, the most time consuming and complicated way of doing a pattern, but it can be the only way to create high-quality versions of some types of patterns.
For the purposes of this tutorial, I will be demonstrating a 4-colour pattern using Illustrator. You can do your patterns in any number of colours from 1 to 4 - 4 is the most complicated.
Step 1 - Import the Image
Step 2 - Vectorize
When you're done, you should have all the basic elements of the pattern roughed out in vector shapes. Don't worry if they're not exact - nobody's going to see your original, only the result. Make sure to group important parts as you go along.
Step 3 - Define Colours
It doesn't matter what colours you use here, just that you use no more than 4 of them and that they're different enough from each other that you can tell at a glance what's what. You can define lighter and darker versions of the same colour, as you can see I've done - I'll explain further on how to handle those light/dark colours.
So for mine, I have white, mustard yellow, red, and blue, with the blue in lighter and darker versions.
Step 4 - Tilegood tutorial on doing the tiling.
Rasterizing the Image
After you've got it all done in vector, you need to get it into a raster format...
Step 5 - Colour Separate
Now comes the annoying and tedious part - separating each colour into black and white/greyscale images.
A note before we begin - there is a layering effect that happens with the separate colours, so arranging them in the proper order is important. Red is the bottom layer, green above that, blue above that, and alpha on the very top. You can overlap colours.
Screenshot and paste into your document as a new layer, so you should now have 4 layers above the background, each with a different set of colours as white/greyscale.
Step 6 - Finish Image
Resize to 256x256. If you're using Photoshop, make sure to change the resize setting to Bilinear or you'll get seams around the edges, which will be visible in-game. It's usually okay if your image is a little bit distorted, if it wasn't perfectly square when tiling - again, nobody will be seeing your original image, just the result, so they wont' know it's distorted.
Next, take each layer from your 4-layer tiled document and copy it, and paste the contents into a different channel in the new document. Remember the layering if it's important to your pattern - red on bottom, alpha on top.
If you're using Gimp, it's a little silly - once you've Decomposed to split into channels, you can paste your different images as new layers and then rename them - red, green, blue, or alpha. You can't paste directly into the channels themselves.
When you get them all pasted and look at the RGB channel, it should look, well, pretty weird. You may not be able to see anything on the alpha channel very well. Flip through your channels to make sure you've got it all set up properly.
If you're in Gimp, you'll have to do Colors - Components - Compose to smush it all back together, and it won't look right at all after that - Gimp's a little weird like that.
In Gimp, Compression should be set to None, Format set to RGBA8, and tick Generate Mipmaps. If you get an error complaining about volume maps, just ignore it.