MP3: MPEG 1 Layer 3

The MP3 algorithm development started in 1987, with a joint cooperation of Fraunhofer IIS-A and the University of Erlangen. It is standardized as ISO-MPEG Audio Layer-3 (IS 11172-3 and IS 13818-3).

It soon became the de facto standard for lossy audio encoding, due to the high compression rates (1/11 of the original size, still remaining considerable quality), the high availability of decoders and the low CPU requirements for playback. (486 DX2-100 is enough for real-time decoding)

It supports multichannel files (Although there's no implementation yet), sampling rates from 16kHz to 24kHz (MPEG2 Layer 3) and 32kHz to 48kHz (MPEG1 Layer 3)

Formal and informal listening tests have shown that MP3 at the 160-224 kbps range provide encoded results undistinguishable from the original materials in most of the cases.

Pros

Widespread acceptance, support in nearly all hardware audio players and devices
Transparent quality at --alt-preset standard (LAME) in most of the cases.
An ISO standard, part of MPEG specs
Fast decoding, lower complexity than AAC or Vorbis
Anyone can create their own implementation (Specs and demo sources available)
Relaxed licensing schedule

Cons

Lower performance / efficiency than modern codecs
Problem cases that trip out all transform codecs
Slow encoding (Using LAME VBR)
Sometimes, maximum bitrate (320kbps) isn't enough.
No multichannel implementations.
Unusable for high definition audio (sampling rates higher than 48kHz)

Techniques used in compression

Huffman coding
Quantization
M/S matrixing
Intensity stereo
Channel coupling
Modified discrete cosine transform (MDCT)
Polyphase filter bank

There is a non-standardized form of MP3 called MP3pro, which takes advantage of SBR encoding to provide better quality at low bitrates.

LAME Encoder

LAME (LAME Ain't an MP3 Encoder) is the recommended encoder. It has been developed by the open-source community since 1998, and has become the highest quality encoder for most purposes.

LAME contains presets to provide the consistant high levels of quality across all songs. These are the recommended switches for using LAME with good reason.

Additional reading

MP3 at Audiocoding Wiki
MPEG1 Layer 3 - Technical explanation of MP3 encoding.
Roberto's listening test featuring MP3 encoders