Begin by making a new Layer and name it 'Grunge Texture',
Set your colors to default by pressing D.
Now use Photoshop's Filter>Render>Clouds.
Tutorial Step 2
Go head and select the Smudge Tool (R), And set it to the Spatter Brush (Size 59).
Goto Photoshop's Window>Brushes and Select Shape Dynamics, Set Size Jitter to 100%. And begin making short strokes across the Layer.
Tutorial Step 3
Keep repeating the brush strokes until you're satisfied with the outcome, Now goto Photoshop's Filter>Noise>Add Noise (Use about 2-5%)
Tutorial Step 4
Now duplicate the 'Grunge Texture' Layer. On the Duplicated Layer Goto Photoshop's Filter>Sketch>Charcoal (Settings).
Set this Layers Blending Mode to Overlay and then set Opacity to 50%.
Tutorial Step 5
The above is what i came up with. You can Play with the Hue & Saturation to Change colors, Experiment with different Filter Settings to fit your taste.