Dirt Layers

If you don't absolutely need 4 colour palette options for your pattern, you can use one of those options as a "dirt" or "grunge" layer. Usually people offer both clean and dirty versions of their patterns if they do a dirty version (since dirt can't be turned off, just minimized by changing its colour to match the rest of the pattern) but it's quite easy to add dirt, and a lot of downloaders love having grungy icky unclean run-down houses.

Remember, when creating patterns, white is fully opaque, and black is fully transparent. So what we need to do is create a random, blotchy sort of image that's mostly black with some very dark grey and a few areas that are lighter, but not fully white.

The easiest way to do this is to use a simple filter. In Photoshop, try Filter - Render - Clouds. This automatically creates a seamless texture. You can then adjust the brightness and contrast so it's mostly dark with a few light-ish areas.

It's better to create a large document (1000x1000 pixels or so - exact size doesn't matter) than to do it on your smaller 256x256 document, as it will give you more variation - more areas of light and dark instead of just a few. You can then copy the clouds and size down. Or if you're feeling lazy, just save the image at right and use it.  ;)

Of course, you don't have to use clouds - you can use any natural random looking texture that's seamless and has good variation between light and dark.

Once you've got a good texture for a dirt layer, Select All and Copy it. Then switch back to your main document. Your dirt layer needs to be the top layer, so you'll put it on the last channel. So if you've got a single colour pattern (that uses only the red channel) then dirt goes on green. Two colour (red and green), the dirt goes on blue. Three colour (red, green, and blue), the dirt goes on the alpha channel.

I'll cover a little more on handling of dirt layers in the Pattern Packager in the section on packaging up your pattern for use in-game.