Ogg Vorbis is the opensource-successor of mp3. It provides higher compression rates with better audio quality. In Linux, the ogg vorbis format is already the standard format for audio compression and everything necessary to create/playback ".ogg"-files is already included.

FLAC stands for Free Lossless Audio Codec. Grossly oversimplified, FLAC is similar to MP3, but lossless, meaning that audio is compressed in FLAC without any loss in quality. This is similar to how Zip works, except with FLAC you will get much better compression because it is designed specifically for audio, and you can play back compressed FLAC files in your favorite player just like you would an MP3 file.
You can download the encoder from http://flac.sourceforge.net.