XMMS is the classic "Winampesque" program for Linux. It has more or less the same advantages and disadvantages as Winamp does. Skinnable; but doesn't usually integrate very well with the desktop, has some good plugins, really easy to build ad-hoc playlists, etc. I use XMMS for various special purpose, one time, sort of things e.g. playing small batches of files before deciding to commit them, or not, to my standard library. It is also a perfectly good default player.
I use Amarok for day to day stuff, as it is nice for dealing with a big, largely static library. It is a KDE app,so it doesn't look quite right on a GNOME desktop; but it's a lot closer than XMMS.
Rythmbox is the GNOME native app that ships with Ubuntu by default. I don't know much about it, as it rubbed me the wrong way for some reason I can no longer remember, and I stopped using it ages ago. It is probably fine; but I'm not the one to tell you.
Now, an important thing to know about media players in Linux(and on other platforms as well, oftentimes) is that they typically depend on codecs that lurk behind the scenes. XMMS has one set, you'll find them if you do a search in Synaptic for "XMMS"(possibly only if universe is enabled, which I recommend, incidentally). At very least you'll probably need XMMS-mad which handles MP3 playback and probably XMMS-cdread which allows you to play right off audio CDs.
Most other audio apps either do, or have the option to, use Gstreamer, a unified framework for audio and video. Indeed, Totem and Rythmbox are basically just minimal interfaces that talk to Gstreamer. You'll need to obtain the necessary plugins; but once you do, all Gstreamer apps will have the same abilities. Do a synaptic search for "Gstreamer" and you'll get the list. Gstreamer0.8-mad , for MP3 is probably a good start. Gstreamer0.8-cdparanoia, for CD playback wouldn't hurt, and from there it is up to you.
I've also heard that Realmedia, of all people, decided to skip being evil beyond all mortal measure(shocking, I know) when they did Linux support, so their Helix player is actually open source and their RealPlayer, while closed, isn't horribly vile like the Windows version. I note this for the sake of completeness; but I don't recommend tainting your system with proprietary binaries unless you really need to(This is partly a technical thing, closed source stuff is, on the whole, more likely to seriously muck things up than open stuff is, just look at the ATI drivers versus the open source ones, for example; but it is also a ideological thing on my part. I run an open desktop for more than just technical reasons. You would be well advised to pay heed to the technical side, whether or not you listen to the ideological side is up to you. Just in the spirit of full disclosure and all.)
Also: a general word on Linux handling of audio and video formats. There is a sort of hierarchy of support for them, that pretty much depends on their openness. The fully open formats, Vorbis, Theora, Flac, Speex, etc. are more or less perfectly supported. Most distros ship with them, pretty much all make installing them easy. Common formats of vaguely questionable oppenness, e.g. MP3 are usually well supported; but distros often don't ship with them, to avoid possible legal entanglements. DVDs fall somewhere into this category as well. The video is just MPEG2, and thus well supported; but the DeCSS is a legal grey area. Pretty much no distro dares ship with it; but support from third parties is quite good, as the format is well understood and the software is open, just somewhat legally iffy, in certain jurisdictions. The worst are formats that use proprietary DRM schemes or are otherwise encumbered. These will pretty much not work without a decent amount of futzing, often involving using codecs designed for Windows, and may not work at all.
Obviously, in many cases, you have no choice. Your music gadget of choice only works with wma and MP3, not vorbis, or that video you downloaded is only available in Real format, or whatever; and it is certainly good for your system to be able to play as many formats as you need it to; but you will make your life easier if you use the more open format whenever you have the choice.
Edit: Short answer: you probably need Gstreamer0.8-mad.