Codecs have always been a pain in the butt. Usually I have used the Mallirat deb repositories, but the Ubuntu folks have made it MUCH easier!
Check this out: https://wiki.ubuntu.com/RestrictedFormats
All you have to do is:
-Go to the repositories menu item
-and paste this line (current as of 9/21/2005): deb http://ubuntu-backports.mirrormax.net/
hoary-extras main universe multiverse restricted
-Then reload package info (it should do this automatically if you have a high speed connection)
-Finally searc synaptic for a package called lame. This is a pretty good mp3 codec library. There are others as well. Search for mp3 in "Name and Description"
-Install and you're off and running.
Note: last night (9/20/2005) I had an issue with the mirror being down, but it worked fine this morning.