A common comparison you can often find on the internet. Many claims to either side. I'm personally regularly exposed to both. I won't hide: I prefer git and I'll try to explain why.
Edit: almost half year since original post, more experience with Mercurial, so I decided to add some editions, that bring Mercurial closer to Git. I still prefer Git, but the margin between them got significantly smaller since original version. All editions are marked bellow.
Heads vs. rebasing
One of the first things you'll encounter: you commit some changes to your local repo, but push fails, because someone else has pushed before you. In this case Mercurial and Git work differently. In mercurial you pull the changes and end up with two (or more) heads. Heads are actually branches, they're only unnamed. What you have to do is to merge them, commit and then push. You can get conflicts during merge, which you have to resolve.
In Git you execute git pull --rebase. Git rolls back all you commits, pulls the changes and then recommits yours. Each of your commits can fail due to conflict, you have to resolve it then resume rebasing. When done, you can push.
At first glance Mercurial seems simpler. However, this simplicity has one significant drawback: heads are actually branches, that end up in your repository (central, where everyone pushes). As a result your history has a lot of branches and merges, which can be difficult to track, if you have many developers pushing to the same repository. In Git you only have branches you explicitly created, all commits to one branch have a nice linear history, which is much easier to understand.
Edit: there is Rebase extension for Mercurial, which let's you work the same way as in Git, I highly recommend you to use it, nice history is worth it!
Staging area makes everyday work easier
Git exposes staging area to the user, while Mercurial doesn't. Again, on paper Mercurial looks simpler - you only execute add for new files, it's enough to execute commit for changes. With Git there's no difference, whether you change or add file, you have to execute add on it be fore you do commit (there is a shortcut: git commit -a).
In real life I find Git simpler to use! Why? I like to check the changes before committing, so I execute diff on each file. If it's fine, I execute add on it. This way Git tracks reviewed files for me. With Mercurial I have to keep it in mind. Also, sometimes I change a lot of files and then want to commit them in few separate commits. With mercurial I have to list all files to a commit command, which can be complicated. With Git I simply do add each desired file and then commit. In this case Git is perfectly usable from command line, while with Mercurial I'm forced to turn to GUI tool.
Edit: Mercurial seems to have alternatives to this, Mercurial Queues (MQ) extention. I only looked a bit at it's documentation: at first glance - more options, but harder to use. I think I'll stick with shelve/TortoiseHG for now (and I still like Git's way).
Status is status
Git status gives you more information than Mercurials. On Mercurial you get a list of new/modified/removed files. Git gives you this too, but it also tells you the current branch and a number of commits in it, that haven't yet been pushed. It will also tell you, if it is known, that your branch was rebased to some older revision. On Mercurial I have to execute multiple commands to get the same information (and I often do, especially hg outgoing).
In Git you can commit and undo commits, there's nothing restricting you from doing that, except the repository you push to. You can do multiple commits locally and undo them, if you haven't pushed them yet. Mercurial puts restrictions on this, hopefully there are plugins that can help you.
Git often does less-like interactive output
In particular, if you do git diff or git log, the output often will exceed the number of lines in your console. Git automatically applies less style control on it, so you can browse the output. Mercurial just dumps everything to console, so if you do hg log without any arguments, the next thing you do is press Ctrl+C.
More power from git add
The git add has a nice feature, called patch mode. Not entirely easy thing to use, but can save you a lot of time on certain ocasions. It allows you to commit only some changes made to file, rather than all. I recommend to learn to use it for everyone, who uses Git.
git commit --amend lets you change the message of your last commit. Saves a lot of time, when you commit and suddenly realise you forgot to enter something like bug number into a commit. This also let you to add a file or change you missed.
Edit: Mercurial has Amend extention, but be careful with it, it not only let's you change commit message, but also adds (merges into) all pending changes to the last commit, so just changing commit message is not so simple.
A good word about Mercurial
Certain parts of Git has to be learned. In particular git rebase, where you need to understand, how it works, and to know what commands to execute, when you get conflicts. hg outgoing nicely tells you all the changes you're going to push from all branches. hg incomming does the opposite. I'm certain Mercurial has some more nice things that Git lacks.
Edit: Mercurial lets you pull or switch branch with pending changes
Initially writing this I missed the rather obvious feature in Mercurial - it let's you pull or switch branch, when you have pending changes. Git doesn't let you do that, it requires you to have a clean local directory first (all committed, no changes, except untracked files).
Although the above might look like criticism of Mercurial, this wasn't the intent. Both are great version control systems, far better than Subversion. It's up for everyone to choose. It simply learned Git first, read a lot on the internet about Mercurial having less features but being simpler, and finally started using Mercurial in my job. And I think this "Mercurial is simpler" is a nonsense: easier to learn - probably, easier to use every day - I really don't think so!