Wow, I can't believe I've been using iTunes for all this time and just figured this out. In iTunes, you can down-sample your existing MP3s to a lower bit rate. Why do this? Well, I used to rip my CDs at a high bit rate, but now that I have an iPod I want them at a lower rate.
It's simple, just set the bit rate you want in iTunes' preferences, and select the songs you want to down sample. Then under the Advanced menu, select "Convert Selection to MP3." Thats it! Done (after you trash the high bit-rate songs of course). I can now fit many more songs on my iPod!
You can also up-sample to a higher bit-rate if you want, but I wouldn't recommend it, the quality isn't going to get any better.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20030215215022754