My last post talked about compiling ffmpeg on Ubuntu, for use with Drupal's op_video plugin. I then had to do the same thing on a Debian 4.0 server, and found that I had to compile literally every library from source, which means all of those handy apt-get lines do nothing for you. Here are the packages that you need:
A few of these are dependant on the other (for example, ogg is dependant upon vorbis, or the other way around, forgive me, I can't quite remember). For most of these you'll do the standard ./configure; make; make install. However, make sure to look at the README files to see if you need to do anything different for your environment.