Brush would be one way and depending on the brush, not that time consuming, as you could do it in one swoop, but the first thing that comes to my mind is using a photo of a specific texture.
This is a concrete texture I googled for this example. I chose this one specifically, cause it's got those air bubble holes that are like dark speckles waiting for you to harvest them.
- Turn the image gray:
Image > Adjustments > Black & white...
- With levels:
Image > Adjustments > Levels...
- Bring the upper white arrow to the left as far as you can, so that it's almost all white. Then slide the grey arrow closer to the white. The goal is to get rid of most of the grays and and be left with black speckles on a white background. ( Every image will be different. )
- It might be easier to get it kinda close, apply that and do
Levelsagain. This gives you finer control over those last few gray pixels you wish to push to black.
To easily blend it to the colored background:
- Set it on top of the background color ( in its own layer of course )
- Set its
Multiply. This gets you half way. You could potentially just lower the opacity at this point and be done with it, but I'd keep the opacity at 100% and do the following:
Image > Adjustments > Hue & saturation...
- Turn on
- Set hue to your liking
- Add some saturation if needed
- Add some light
- Turn on
Remember that you can also stack these textures. For example, If you want to have more of the bigger speckles, you might be left with just a few of them, but you can compensate by either duplicating them or adding more textures to the mix... or just find a texture that is perfect to begin with.