Since I often answer these questions, I thought I'd write them down here. A list of some very recommended free software is on the right.
1. Choosing a bitrate to encode at
MP3 encoding is a trade-off between quality and filesize. 128kbps has become a standard for internet downloads, but I personally prefer to use at least 192kbps. The reason for this is because most encoders throw away everything above a 16kHz frequency cut-off at standard quality. The 16-20kHz frequency range includes instruments such as hi-hat cymbals and other treble. Here's a frequency analysis of the same song at 128kbps and 192kbps.
These results, displayed in Soundprobe, were generated using the Lame encoder supplied with CDex 1.5 set to Joint Stereo in each case. For 192kbps, the 'High' quality setting was also used. Quality settings are only really effective at bitrates of 192kbps and above.
As an additional tip, I'd suggest using Joint Stereo because this provides a significant quality increase when encoding quasi-mono signals, which most CD music uses. Basically, less bitrate will be used on sounds which are the same in both channels, meaning more bitrate is available for parts of the sample you're most likely to hear.
Quality tip: If you have no requirement for CBR (constant bitrate), LAME has a preset which provides almost perfect audio reproduction at approximately 192kbps. This uses as much bitrate as is appropriate for whichever segment of audio is being encoded. To try it, enter the following parameter into your software: --alt-preset standard
(This setting is also on the 'Quality' menu in CDex, which uses a DLL rather than the EXE, so you can't use command-line parameters directly.) The preset is great for copies which you know you'll want to keep, but usually takes a little longer to encode. It's a trade-off; you spend more time encoding in the short-term, but the result is worth it.
2. Using MP3s with portable players
MP3 players which store files on flash memory (rather than CDs or small hard-drives) tend to offer relatively little space; 64Mb is still quite standard. At 128kbps, this gives us a little over an hour to play with. However, we'd prefer better quality, 192kbps.
What I suggest is to take the Joint Stereo advantage to its extreme: convert the MP3 to mono at half the usual bitrate. In my case, that would be 96kbps mono, 44,100 samples per second with 'High' quality set. Since it's awkward to keep changing settings and use CDex to convert files, here's my suggested routine. This also lets you set a playlist with any MP3 player, even those which don't support .pls or .m3u files and play everything alphabetically.
3. Some terminology explained
Bitrate: How many kilobits (space) is used to store data, usually a constant value per second... eg, 192kbps, 96kbps. Note that 1 bit = 8 bytes, so kilobits shouldn't be confused with kilobytes, and that 'kilo' usually means 1024 (rather than 1000) when talking about computers. If you're confused, don't worry. Just see the above sections for suggested values. Some older hardware can't handle ABR or VBR (average and variable bitrates, respectively) but anything recent should be fine.
Mode / Channels: At its simplest, two channel (stereo) or one (mono)... you can also specify Joint Stereo or Forced Joint Stereo. Joint Stereo takes advantage of similar sounds in music to produce better quality files. Forced Joint Stereo applies this more aggressively, so channel balance may be altered — it may begin to sound more mono.
Lame: Stands for "Lame Ain't an MP3 Encoder". Probably the best free MP3 encoder.
Quality / Optimisation: Allows you to choose whether your MP3s are optimised for speed of encoding or quality of playback. Using the Lame encoder, 'High' quality usually makes little difference unless encoding at more than 128kbps; use 'Standard' if you are.
Frequency cut-off: Something encoders tend to do at bitrates of 128kbps or even higher bitrates unless 'High' quality optimisation is selected. Usually this cut-off will be above 16kHz... unfortunately, most people hear frequencies up to around 18kHz, so if this cut-off occurs, audio quality suffers. Try 192kbps (or a higher bitrate) and the 'High' quality setting.
Sampling frequency: Not to be confused with the frequency range above. This is how many tiny bits of data are stored every second to reproduce sounds digitally. CD is 44,100kHz, radio is 22,050kHz and some old VCRs are 11,025kHz. Most music you encode will need to stay at 44,100kHz in order to preserve quality — live concert recordings less so.