Stereograms consist of two parts: The depth-map and the tiled image. The tiled image is what you see at first. The depth-map is the hidden 3D image. This tutorial will show you how to create the tiled image without having to paint a single stroke! Made for Paint Shop Pro 5, but I guess similar results can be achieved with other good paint programs.
Create a new image

Fill it with a medium grey color.
Tile it

Now create a new image twice the size the original (20x80).
Paste the original image into the new image 4 times so that it precisely cover all of the new image ( highlight the new image and use edit > paste > as new selection ). You can now throw out the original image.
Resize

Adjust the colors

Change the hue, saturation, and lightness ( colors > adjust > hue/saturation/lightness. Set hue to 50, saturation to 100, and lightness to 0 ).
Then make it a little more colorful ( colors > adjust > brightness/contrast. Set brightness to 0 and contrast to 40 )
Add a little noise, 10% or so. That's because the tiled image in a stereogram has to be detailed to work well.
Crop it

That's all

Experiment with other sizes, filters, and effects. Instead of starting out with a plain grey color you can also use an image of yours or quickly make something colorful. There's a lot of possibilities!
Remember to let me know if you make some stereograms of your own!