Testing by Fraunhofer and Thomson found that for mp3s, 256 kbps was true "CD-quality"; that is, their sound engineers could rarely tell the difference between mp3s encoded at that rate and the original CDs. These files were roughly 20% of the original filesize, but virtually indistinguishable in quality.
Since then, 128 kbps mp3s have become the "standard". Although most people with good equipment can hear the difference, they still sound good enough for the average listener. These files are roughly 10% of the original filesize, and are the source of the 1 megabyte per minute rule some stores quote for determining how much music you can fit on a given portable mp3 player.
People with dull ears, bad equipment, or an strong desire to fit twice as much music on a portable player encode mp3s at 64 kbps. These files sound not much worse than FM radio, and are a mere 5% of the original filesize. (Most, but not all, portable players that advertise "stores over 2 hours of music" are assuming the use of 64 kbps mp3s, rather than the more common 128 kbps mp3s.)
The problem with these rules of thumb is that they only work for mp3s. There are now many formats newer than mp3 which all improve on sound quality. And, as more sophisticated psychoacoustic models are developed, the difference in sound quality between one bitrate for mp3 and the same bitrate for a different format will only continue to widen.
For example, a file encoded in the Ogg Vorbis format at "quality 3" typically results in an average bitrate of 112 kbps but sounds better than an mp3 at 128 kbps and often as good as an mp3 encoded at 160 kbps.
For this reason, the Ogg Vorbis community discourages users from trying to achieve a specific bitrate when encoding but instead to concentrate on sound quality. In fact, the Ogg Vorbis format encoders don't normally consider bitrate at all (the default mode of operation is VBR), instead using a "quality" rating, which ranges from -1 to 10 in increments of 0.01 or so. This quality rating is a measure of how close to the original the compressed file should sound; the encoder uses as many or as few bits as necessary to satisfy the quality requirement. Each quality setting results in a rough average bitrate for a piece of average music, but this is a by-product of how the encoder has been tuned; the encoder does not aim at any particular bitrate.
The default quality setting is 3, which should be fine for the average user since it gives sound quality better than a 128 kbps mp3 but is over 10% smaller. Someone wanting sound almost identical to a 128 kbps mp3 can usually get by with quality 2, which sounds as good but is 25% smaller.