it highly depends on the player/encoder
if you're going to use mplayer, you'll need to first compile the specific xvid-codec (sorry, dunno where to get koepi's build, google for it, but be sure it's the source-release for linux, most probable a *.tar.gz or *.tar.bz2)
and then you'll have to compile mplayer (mplayerhq.hu to get the sources)
there you'll have to make sure in that the ./configure says that it will compile with xvid as output-codec, that's the installation of the xvid-codec and mpalyer o.o
for codecs like divx5, rm, qt, vivo, etc. as input you'll need to get the hacked windows-versions from mplayerhq.hu and also install them before you compile mplayer (see mplayer's installation-manual)
(there are easier ways i think, but i dont know any atm, so please dont ask for a 3 click-way)
P.S.: nobody bothered with this too much and got a movie re-encoded the correct way with mplayer by now afaik, so i'd suggest to stick to vdub, especially as linux-newbie