Long description short: The Codec is the instruction manual on how to read then play the music (or video, but we'll use music in this case). It reads the sheet music that says "Put a note here, a voice here, etc" and the end result is the complete song.
So you have the sheet music but if you don't have a musician that can read it, you can't play the sound file. Maybe not the best analogy... Let's change that to include: Many can READ the music, but to write the songs is harder and takes a songwriter. The CODEC is the songwriter. The playback (MPlayer, etc) is the average musician.
The benefit is that you save tons of hard drive space (and bandwidth).
You don't often need the CODEC to play stuff back for common formats. Most already support it. However when you CREATE, you have to have a CODEC to encode it properly so that later it will play. This is what you are running into right now.
I'm running into trouble finding a x64 bit LAME MP3 encoder, for example. They're mostly 32 bit and don't want to work on Win7 x64 that I have, so I feel your pain. Try another format. If you want the space savings, one thing I found that has its own internal CODEC is Super(C). I can save a file with no audio compression, feed it through Super(C) and tell it don't change the video, just compress the audio into Mp3 and it will save tons of space for me.
