lots of texture brushes and a good handling of color and lighting.
Get Mathias' brushes here
http://conceptart.org/forums/showthread.php?t=73169, I think they'll give you the effect your looking for, and I know they have helped me tons.
From what I can gather it seems that you need to splatter the underpainting with heavy texture and color and build ontop of it with basic circle brushes and circled-textured brushes. Your best bet is get a handle on lighting and color in addition to the other fundementals, that way youll be able to turn out stuff like this within minutes...literally
"I was born; six gun in my hand; behind the gun; I make my final stand"~Bad Company