You might take a look at this tutorial by Dave King about one of his techniques for creating texture art. This one is heavily slanted toward use of the Smudge tool in Photoshop, and it's pretty nifty. He's also got a tutorial where he takes you through the process of constructing an orc model, step by step from start to finish. It's a little light on details, and assumes some advanced knowledge, but it's still pretty interesting. He had another tutorial focused explicitly on making texture art, but damned if I can find it now. (It was called "Skin Your Knees" or something like that. Anyone seen it lately?)

Note that the smudge tutorial doesn't deal with coloration, just shading. King's methods in the past have involved doing a grey scale shading map as outlined in the tutorial, then applying color in big blocks using the Multiply layer setting to combine it with the shading information. Which is why I'm mad that I can't find the "Skin Your Knees" tutorial, because he talked about this technique there.