There's a lot of half-truths and misconceptions regarding audio encoding floating around, that could use a good clearing up. I'll just try to summarize the main points.
- MP3 is by far the most popular music compression format with the widest compatibility. It's not really a Free or Open standard (like Ogg Vorbis is), as lots of organizations claim ownership and patents on parts of it, but in practice nobody gives a damn. It's non-proprietary in the sense that everybody can implement it as long as they pay the fees and many implementations are available. If you get a player (either hardware or software) from a brand name manufacturer, they (and by extension, you) already paid the license fees.
- Like most formats, the MP3 decoder is completely fixed in the standard, but the encoder is not, and different ones produce quite different quality. The consensus is that the Lame encoder produces the best output. A lot of older encodings and from lesser encoders aren't very good, which lead some to believe that the MP3 standard just isn't very good. The MP3 encoder in iTunes isn't particularly good, at least in older listening tests. I'm not aware of the MP3 encoder quality in recent iTunes, but I doubt they spent much more effort on it.
- In the majority of cases, Lame MP3 is extremely hard to impossible to distinguish from the CD source for most people with the standard presets, which produce variable bitrate files of about 165 - 245 kbps.
- AAC is a more modern codec that is theoretically better than MP3. The open/proprietaryness is about the same as MP3: lots of organizations claim varying parts of ownership, and everybody can implement it for a fee. More and more big name companies like Sony and Nokia are supporting it, especially in newer devices, but it's still not as widespread as MP3. Basically, everything that plays AAC can also play MP3, but the reverse is not true. Apple has chosen AAC as its default format, but many of the files you buy from their stores have additional encryption applied, called Fairplay. Once decrypted, they're standard AAC, but (officially) only Apple players have the decryption keys.
- Like MP3, the decoder is fixed, but there are different encoders, which compress with different quality. Apple's AAC encoder in iTunes is amongst the best. Nero has an AAC encoder that's roughly the same quality, but it's only available for Windows.
- Although AAC (and other modern encoders, like WMAPro and Ogg Vorbis) are theoretically better than MP3, most of the advantage are for lower bitrates. 64 or 96 kbps AACs sounds much better than same size MP3. Because most test are meant to show differences rather than similarities, and thus are conducted at lower bitrates where MP3 lose badly, some people believe that MP3 is just much worse than AAC. But at 128kbps, the difference is already pretty small, with maybe around 10% advantage for AAC (meaning that you probably need a 10% bigger file in MP3 to get the same quality as in AAC). At around 160kbps and over, the difference is negligible, which is to be expected, as it's also extremely hard to tell the difference between the 160kbps+ MP3/AAC and the source CD.
- Many people will claim to easily hear differences between [format of choice] and [format they don't like], but few can do it in a fair blind test.
- If you're paranoid (or expect the future may still bring new breakthrough compressions), you should probably use a lossless compression. The relevant ones are Apple Lossless, which play directly on iPods, and FLAC, which is most popular outside of Apple. Since all the information from the source is retained in all lossless formats, and compression ratios don't differ very much, the choice is mainly down to convenience, playback support, and metadata support (titles, album art, etc).
- You can always convert from one lossless format to another without loss of sound quality, but metadata may be lost. Converting from any lossy standard like MP3 or AAC to another will always result in degraded sound quality.