MP3's are OK, but there's better audio format now - WMA (Windows Media Audio, I think, v.8). Audio in this format takes up half the space of original MP3 and the qualityt stays the same. This is quite useful for solving disk storage problems as well as download/upload.

I think there are many programs which convert MP3's to WMA's, but I can recomend AudioSlimmer.

I've also heard there is new format of MP3, called MP4. It's supposed to have same caracteristics as WMA.