What are codecs, and how do they differ?

A codec is a property that every channel (room) on a server has, it's a technical word that describes what technique is used to compress the voice data before transporting it over the internet. To change the codec of a channel, you right click on it and select 'Edit Channel', there you can set the codec that will be used for all further communication in the selected room. Note: You will probably need administrative priviledges [server admin (SA) or channel admin (CA)] in order to change the codec of a channel.
Codecs are usually a trade-off between bandwidth usage and quality, the bandwidth usage (in KBits/sec) is part of the name of each codec that TeamSpeak offers; following we have ordered codecs by quality. Note that quality can not be measured, so the following is just the opinion of the writer of this text.

Quality: (best quality comes first)

Speex25.9 > Speex19.5 > Speex16.3 > Speex12.3 > GSM16.4 = GSM14.8 > Speex9.3 > Speex7.2 > WinCELP5.2 > Speex5.2 > CELP6.3 = CELP5.1 > Speex3.4

What codec for which internet connection?

DSL/Cable or better
For talking Speex 16.3 is easily good enough, if you want to transmit music, go Speex 25.9.

ISDN
Speex 12.3 sounds alright, limit your download to 14 KBit/s if you want to game. Speex 16.3 with download limit on 17 might also be OK.

Modem
Speex 9.3 is still quite good quality. Limit your download to 10 KBit. Note that if you want to game its way to high a setting, go as low as you can bare (Speex 5.2, or even Speex 3.4, limit your download to 6 respectivly 4).