I was recently searching for a CV LaTeX class. I finally found the EuropeCV class and I really like it.
Installing on Debian/Ubuntu
apt-get install texlive-latex-recommended texlive-latex-base texlive-fonts-recommended texlive-latex-extra
I also recommend to use a LaTeX editor. My favourite is Kile.
Using the class
The package provides examples in /usr/share/doc/texlive-latex-extra/latex/europecv/examples/. Choose the example that fits your needs and modify it. A full documentation is also installed in /usr/share/doc/texlive-latex-extra/latex/europecv/europecv.pdf.gz.
Example
Nothing better than an example to make the point… Here is my PDF CV, and the LaTeX source.
Edit on 2011/02/24:
I have recently dropped EuropeCV in favor of the moderncv template, which I find much nicer. I also use the moderntimeline package with it.