I did try Mercurial, but very superficially. I used it with a project shared with Rui, who uses Mercurial and he seems to be very happy with it.
Whatever you choose, I would stick with either Mercurial or Git. CVS is dead, and Subversion is not good enough. And right now, all non-personal projects I work on use Subversion, so I have some experience with it. Of the others distributed systems, only Darcs, still the best out there in terms of day-to-day usage, deserves a honorable mention.
My take on Mercurial vs Git is this:
when I started with Git, Mercurial was better if you need to run on Windows. Right now, Git has binaries available on the home-page but I don't do Windows, so I don't know if it is good enough, or stable enough. On Linux, Git just cannot be beaten in terms of performance.
I'm not comfortable with the code quality of Mercurial. I followed the Mercurial commit list for a month or so at the time, and some of the bugs where pretty nasty. It seems that Mercurial is still fixing core bugs. On the other hand, Git fixes in the past weeks are mostly cosmetic, and reorganization of code into a libgit. Also, the organization of Git release management is very conservative, and that feels good.
I liked the GUI tools that come with Git better than those of Mercurial. I'm usually not a big fan of GUI tools to interact with SCMs but I admit that I've been using git-gui for all my commits. The history browser (
gitk) are virtually identical (probably one of the projects "stole" the code from the other :) ).
git-svn rocks my world. It makes working with Subversion less painful. Mercurial doesn't seem to have nothing as good.
In the end, there are big projects using either of them, so its no big deal. There are also tools to migrate repositories from one to the other, so I don't think there is much risk on any of those two.
I freely admit that I could choose any of the two, but the above 2), the need to keep on working with Subversion projects, and the fact that Git is used to manage the linux kernel, X.org, Samba and OLPC, made me trust Git more than Mercurial.