A video file is comprised of two parts: the video "stream", and the audio "stream" (usually stereo). The video stream is encoded and usually "compressed" to make it a reasonable size. The quality of the images suffers more and more as more compression is done (i.e., the smaller the file, the worse the images). The audio stream is nowhere near as big as the video stream, but it too is encoded and compressed (and again more compression tends to make poorer sound).
The video and audio streams must be decompressed as they are played: they were compressed when they were produced. The software that does this is called a "codec" (COder/DECoder). Video and audio codecs are two distinct pieces of software. Furthermore, there are many different kinds of video and audio codecs, and new ones are developed every now and then. (The newer ones tend to compress more while keeping quality the same and/or improve quality while compressing the same amount.)
Video file formats are *not* the same as video and audio codecs, but rather are ways of combining the video and audio streams together while keeping them synchronized. Two file formats that have been around for years are the AVI format (originally Windows) and the MOV format (originally Macintosh). These formats allow various video and audio codecs to be used. This means that a player may be able to play one AVI (MOV) file but not another, depending on what codecs are used in making the video and audio streams contained in the file. The Windows Media file (WMA/WMV) is a more recent invention, and supports modern high-quality codecs, but these file formats and codecs are proprietary to Microsoft and hence cannot be played except by Microsoft software (which of course is not available for Unix/Linux).
MP4 denotes both a video codec (MPEG-4) and a file format. Various audio codecs may be used: AAC is common (and what we use). MPEG-4 is a recent open standard that supports high quality images with good compression.
Note: The older MPEG-2 video standard is what is used for DVDs. It supports high quality images, but the compression is not as good as MPEG-4.
Technical note: Strictly speaking. there is a difference between a video (or audio) stream format and a codec. A stream format, such as MPEG-4, is a standard for encoding, while a codec is a particular software method for encoding. This means that codecs can be proprietary -- and indeed developers may compete to make the best software -- while adhering to a open standard such as MPEG-4. (In the Windows Media case, both the "standard" and the codecs are proprietary, which limits its usefulness.)