Today I accidentally discovered how to make a pretty interesting texture in either Fireworks or Photoshop (the process and outcome are almost identical in each) and probably many other image editing programs.
First, create a new 3 pixel by 3 pixel image. Now zoom in on the image as far as you possibly can. Select the pencil tool, and fill in the image with some random colors and patterns (you only get 9 pixels to play with in my example).
Now change the image size to something like 400px by 400px and watch what happens!
It kills me how simple this is, yet gives a nice effect. As you are playing around with it, try different starting sizes and ending sizes for different effects.