RhythmBox is the new music management application for GNOME, inspired by Apple's iTunes?. Playlists are organized by the information in the music files' tags (be they MP3 or OggVorbis or another format). There's also a "tuner" interface for streamed internet radio.
It is built on top of the the GStreamer framework so it will theoretically support just about any imaginable format. It also uses the GNOME VirtualFileSystem libraries which allows you to add files from sources like ssh://somehost/some/path/foo.mp3__ or smb://hostname/share/name/bar.ogg__.