Both Git and Mercurial are DVCS, and that's great. I wonder if there is a list of particular situations when one of those systems are preferable, something like 'In mobile development for many platforms git is better because ...'.
Are you and/or your team Windows based?: Mercurial is less hassle to use/set up than Git, since it kind of needs you to install a bash console (you can use cygwin instead though).
If you are linux/mac based, either choice is fine, but you might like git more because of all its power tools.
Experience with DVCSs
If you are new to DVCSs, choose Mercurial. If not, try git. Git has lots of toys that might make your learning curve somewhat steeper, Mercurial, OTOH, you will learn in a breeze. Read http://hginit.com/ for a very comprehensive guide.
Also, read http://hginit.com/00.html if you come from CVS/SVN.
Mercurial is a full-featured DVCS, git OTOH I'd even say its almost a DVCS framework (check this cheatsheet out) that can support more specific workflow cases for very big teams/projects.
Also, very importantly, git lets you change your repository history, which can be considered a bad thing (); Mercurial does not let you change your history.
In general terms, I'd say git is overkill in a good way. Personally, I use both mercurial and git, but I always teach mercurial to my coworkers
There is no wrong choice
Actually and IMHO, you should learn both, but always start with Mercurial. Too really see how they compare (which are really somewhat smaller details) I recommend you reading these two articles:
The path of the DVCS
Try mercurial first to make your introduction to DVCSs way more pleasant. I've seen a lot of people rant their way into git and end up loving it, but OTOH I've seen people make their whole way into mercurial in complete awe. After that, if you feel mercurial is not enough you can continue your path with git seamlessly.
Update: Mercurial is now better at letting you modify the history, see:
You should use git when a project or community you want to contribute to uses git, and use Mercurial when they use Mercurial. It may seem obvious, but the community is more important than the tool.
I would suggest learning both, since they are so similar in many ways, that way you can contribute equally easily to projects and communities that use either.
For example, if you are starting a project to develop a Linux device driver, git is the obvious choice, whereas if it's a python project, hg would be logical.
An excellent description of why Python chose mercurial can be found on the Brett Cannons blog, which links to his paper PEP 374 -- Choosing a distributed VCS for the Python project which documents their decision making process.
Alas, I couldn't quickly find an equivalent paper for a community which chose git instead.
Generally Mercurial is easier to learn than Git
So use Mercurial (Hg) if you want to learn distributed version control and get your pet project off the ground real quick.
We used SVN, than migrated to MERCURIAL and recently to GIT. Git has some immediate advantages over hg: stashing and the index (simpler atomic commits). Than you'll appreciate the easy branching. You will regret git and miss hg when something goes wrong or when you need to deeply understand some concept like "rebasing" or "fast forwarding". I really hate to have to dig into the options madness of git when I need to do something trivial like "svn revert"... In conclusion: git does too much for the majority of projects that are using it and the learning curve is too steep. (ah, and I really laugh when "git stat" says "Did you mean status?" - I know, alias, I know...)
For some time, Mercurial worked better on Windows than Git did, and that was a reason to use Mercurial. It's also generally easier to get into.
Both Mercurial and Git will do pretty much what you want with a DVCS. There are differences, but they're unlikely to matter in day-to-day operations for most people. Learn one first to get the concepts down, then you can learn how to use the other quickly whenever you need or want to.
I think it all depends what platform you use. I decided on using git on PHP project that I knew everyone was using *nix because they had no problems typing in commands in.
For my other PHP project we have a lot of people using windows as well as mac and linux. It was a breeze to use Mercurial all of those platforms.
Also I think what is also good is the fact that both NetBeans and Eclipse offer support for Mercurial pretty much out of the box. Last time I tried using git on Eclipse it was very bad and i ended up using console. (It was few months ago)
I think it is better to learn one and then read one of the tutorials that shows you command differences etc. Learning two at the same time will just frustrate you because of some small command differences.