It's important to keep in mind that MP3 (or, correctly speaking, mpeg-1 level 3) is a lossy compression algorithm that relies on the way your brain and ears work. A good encoder (like lame) can do a wonderful job and generate a decent mp3 file, whereas a poor one (like bladeenc or any of those xxx-jukebox that use a xing encoder) will cut out high frequencies and introduce artifacts, annoying the hell out of you.

The most common problems with mp3 files:

• Lack of high-frequencies (music sounds flattened).
• Artifacts (undesirable features introduced by the encoders).
• Clicks and Pops (normally introduced by incorrect ripping).

Some guidelines I use when I create my MP3s:

• Use lame as the encoder.
• Use cdparanoia as the ripper. This is for linux. I've heard there are some very good ones for windows too.
• 128Kpbs: only when I want to send a preview of a song to someone.
• 160Kbps: a little better on the high-frequencies.
• 192Kbps: A good trade-off, if you have a little bit more space to waste.
• 256Kbps: Almost archive quality. Big files, but also good quality
• Variable bitrate: The best deal for me. I set the quality to 2 (1 is the best, 7 is the worst), minimum allowed bitrate to 64Kbps and maximum to 256Kbps. With these settings, the encoder will vary the bitrate dynamically between these two values (it's actually fun to watch the bitrate changing while the music plays). The nice thing about VBR is that most songs have periods of silence that can be safely encoded at lower bitrates, saving space. Allowing the encoder to go as high as 256Kbps guarantees quality in some parts of the song. On the average, songs will stay around 180Kbps, but bits will be allocated where they're actually needed.
• Use CRC on your MP3 files (that allows you to detect file corruption).
• Use tags. They help a lot when you want to classify you collection.

Some caveats:

• Some players don't like CRC information (I believe there's an AIWA car player that won't play MP3s with CRCs)
• Some players don't like VBR.

That's not the trend though. I don't believe you should trade VBR and CRC error correction for compatibility with some obscure players.

Let us establish some solid facts as a basis for this matter. The SPL limit for human hearing is approximately a little less than 10 dB of volume in the most sensitive frequency ranges(the same ones used for speech). The frequency limit of human hearing is approximately 20 to 20 000 Hz. If you(yes, you) are using a regular $150 CD player, you probably have nothing better than a 20-bit DA converter connected to regular $300 speakers and an average 0,5% THD stereo amplifier built with ICs instead of discrete components. Its signal-to-noise ratio might be 70 dB or so. Of course a lot of people out there are audiophiles extraordinaire, but since they are already pissed about every part of the abovementioned stereo, they have bigger fish to fry than mp3.

Some people state that "when mp3's are encoded, specific frequencies are removed and discarded, frequencies that are said to be unheard by human ears." This is not true. If you look up a textbook on human hearing, you will notice that the sensitivity of your ears is not uniform throughout the frequency range 20Hz-20Khz. Instead, you have a lot better hearing in the middle of that spectrum. Mp3 uses this(and a lot of other physical facts, not just psychoacoustics) in order to compress music as carefully as possible. Few people complain about the bass in mp3s. Some people complain about the treble in mp3s. A lot of people complain about the midrange in mp3, especially about the elusive "warmth" of the sound. Snake oil aside, it is a scientific fact that this is the frequency range where human hearing is the most sensitive. It is also where the mp3 algorithm does the least of its compression. In fact, the test song used during the development of the mp3 algorithm was Tom's Diner by Susanne Vega.
why? Because Karlheinz Brandenburg, lead of the mp3 development project at the Fraunhofer Institute for Integrated Circuits, used it during testing specifically out of a need for "warm" vocals.

Some people refer to failures of mp3 compared to CDs. The mp3 algorithm has the unfortunate disadvantage of being based upon the abilities of the compact disk. Tomlinson Holman, who developed the THX standard and coined the term "5.1 channel", has suggested an ultimate goal of 10.2 sound, with an array of seven speakers covering the front of the room, plus three speakers in the rear area and two subwoofers, one on each side at 180 degrees.
Does it still sound like mp3 is the issue you have to worry about? Isn't it possible that a 256 kbit, 96 kHz, 10.2 channel mp3 ripped from DVD-audio might be a whole lot better in every way than CD?

Courtney Love has publicly stated that she thinks mp3s sound like shit. She did this in a speech where she also spoke at length about how bad the availability of alternative music on Napster is. Isn't it possible that the fact that most of the music on Napster is encoded by everyone and their dog at 128 kbit or les, downsampled to 22 kHz or ripped from scratched records might have something to do with it? Can you honestly tell the difference between a 192 kbit mp3 ripped by a dedicated mp3 piracy group and distributed with an .SFV file to verify data integrity and ripped from a new, unplayed and clean original CD? Can you do it even on the aforementioned $600 stereo?