Apple - Discussions - Replacement foam earbud covers
It took weeks of moderately persistent research to find this data, but now that it's known it will be everywhere :-).
iPod replacement foam earbud covers: Radio Shack part # 33-376
Here's the RadioShack page for ordering the replacement earpads (http://tinyurl.com/m0qu). A set of 4 is $2.00. I think they're a bit cheaper at some retail outlets.
http://headwize2.powerpill.org/faqs.htm covers getting replacement foam covers for other earsets.
[meta: earpad, earset, earphone, earbud, in-ear, headset, micro, iPod, earphone, foam pad, foam cover, jfaughnan, jgfaughnan]