I like Mercurial as a version control system because it is cross-platform (written in python) and is distributed (meaning it doesn't require a central server to function). I use it on windows quite extensively and was one of the pieces of software that I needed on Linux. The other piece that I needed was TortoiseHG. It is a graphical front end to mercurial and works well.
To install mercurial you'll need to navigate to the MercurialPPA and follow the instructions listed there. The instructions indicate that you'll need to add the following urls to synaptic repository listings:
deb http://ppa.launchpad.net/mercurial-ppa/stable-snapshots/ubuntu jaunty main deb-src http://ppa.launchpad.net/mercurial-ppa/stable-snapshots/ubuntu jaunty main
After mercurial has been installed you can install tortoisehg. The information can be found here at the TortoiseHGPPA
You'll have to add a couple of urls to synaptic's repository listings:
deb http://ppa.launchpad.net/maxb/ppa/ubuntu jaunty main deb-src http://ppa.launchpad.net/maxb/ppa/ubuntu jaunty main