When it comes to multimedia software most Linux distributions have one thing in common: no proprietary codecs - and this might include MP3 playback. I have no deeper insights in the license terms of the MP3 codec, but there is a whole website about it by THOMPSON, the company claiming to control MP3 licensing: mp3licensing.com. There are other proprietary codecs as well, i.e. "aac" which I think is the default file format for Apple's iTunes and devices by Nokia and Sony. Wouldn't it be nice to not care about this crap? The open source alternative is "ogg vorbis", providing great quality audio files and high compression at the same time. So, how can you switch from mp3 to ogg?
If you already have a large collection of MP3 files I guess it wouldn't make any sense converting them to OGG (though possible). Just keep them as they are. But you could start ripping your new CDs to OGG and go on with this format.
If you're interested http://www.vorbis.com/ would be a good starting point.