Up until recently, I've been a big proponent of those big 'ol boxes of 3M foam ear plugs you get at the hardware store. And, I still am. But, there's a better alternative.
Reusable ear plugs:
They go on a little case on your keys, so you always have them before you hop on the bike. the only times I haven't worn earplugs were all because I didn't have them handy at the time or I'd simply forgotten until I was halfway down the street.
I bought these specific ones:
Linky-poo
As some of the reviews stated, they don't seem to work when you put them in at first. but, I loaded up audacity, recorded some static, and set the gain and my computer's volume to a painful level when over-the-ear headphones are worn. Then, I wore the earplugs with the headphones. It was comfortably audible and not painful at all. You can try this yourself, if you don't believe me. Just find some loud noises on YouTube.
I don't know how they work, but they seem to make loud sounds quiet, and have little effect on moderate to low volume sounds. but, I would recommend them. It doesn't even have to be this specific set of ear-plugs, too. As far as I can tell, they're all more or less the same.
Please, be nice to your earholes.