The codec depends on which backend you use. If you use Amarok as your player, for instance, or Kaffeine, the backend can be Xine or Gstreamer for example (Ubuntu uses Xine). So Amarok is the player app, but the actual sound work comes from the backend (like Xine), and you need to get the codecs for the backend. If you use Xine, you'll need to get libxine-extracodecs and after you've installed that, every app that uses Xine as it's backend should be able to play mp3 files (and much more).
First see what backend your favourite player app (Kaffeine, Amarok or something else) uses and then get the appropriate codecs for that backend. If you use mplayer, you'll need mplayer codecs. For Xine, get xine's extracodecs. For Gstreamer, get gstreamer's codec packs (ugly, bad, good etc.)