to expand a little on what Koala says - the file format tells you which type of container the file uses as a transport medium. This may be avi (Audio Video Interleaved) or .mpg, .mov etc. This determines the way the information is stored and delivered.
The codec (
Compression
Decompression) is the algorithms used to firstly compress the video information then as you want to play it to decompress the information - a little bit like going on holidays - you get your clothes, squash them down to fit in your suitcase down then unpack again.
Video files (and to a much lesser extent audio files) are huge if uncompressed - just imagine how much information is needed to describe the position, colour, size etc of every pixel for every frame of a video! then add the audio stream and you would have massive file sizes, making it almost impossible to store and/or transport (either to have as portable files or as in streaming or downloading from the net) these files.
Codecs, to a large extent, determine the file size end quality of the video you watch. If some of the older codecs are used they will not have been able to bring the file size down and retain quality.
The newer codecs such as xVid, DivX, H.264 are able to bring file sizes down dramatically while keeping fairly high quality video - this allows us to store, transport, stream and download high quality video much, much more easily than ever before.
Hope this helps