Go to cgtextures.com and look around in the Grunge categories to find a texture you like. These aren't tiling textures, so download the large ones--you'll need as much resolution as you can get.

Open the texture in PS, and adjust the contrast and brightness until you've got nice splotches and a mostly white background. Paste the grunge into your main doc and place it right above the ground. Set the blend mode to multiply, and it should turn into very nice yuck on the ground.

Since you have so much resolution in your battlemat, you may want to cut out an irregular border around your grunge so that it doesn't make a nice, neat square. Playing with different levels of saturation, contrast and brightness can give a single texture enough variation that you should be able to use it several times without it being obvious that you're reusing the same element. You can throw some grunge on the tents with the same technique. I'd recommend something from the Splatter category for that.