Here's a basic painting of a rocky outcropping (click on any image for a larger version).
Basic rough painting
First I selected and copied as much of the rock as possible, scaled this piece down quite a bit, then pasted it all over the place on a new layer. The resulting texture looks something like this:
Rocky cliff sampled, reduced and repeated to create a texture
Next I applied this as an overlay layer above the main painting layer, and reduced the opacity a bit. This is the original rough painting with the texture over it. Even though the texture clearly repeats when viewed in isolation, this is not apparent when it intersects the larger, similar forms of the main painting on which it's based. Quite the contrary, in fact, the illusion of entirely new forms is created:
The two combined
If the texture layer's opacity is too high it looks cool, but may tend to flatten out the underlying big forms, or its repeating pattern may become evident:
Too much texture?
Fine tune areas of the texture that aren't working well by touching up with the rubber stamp tool, sampling other areas of the texture, and add a layer mask to control precisely where the texture is applied.