I work on Mercurial, but fundamentally I believe both systems are equivalent. They both work with the same abstractions: a series of snapshots (changesets) which make up the history. Each changeset knows where it came from (the parent changeset) and can have many child changesets. The recent hg-git extension provides a two-way bridge between Mercurial and Git and sort of shows this point.
Git has a strong focus on mutating this history graph (with all the consequences that entails) whereas Mercurial does not encourage history rewriting, but it's easy to do anyway and the consequences of doing so are exactly what you should expect them to be (that is, if I modify a changeset you already have, your client will see it as new if you pull from me). So Mercurial has a bias towards non-destructive commands.
As for light-weight branches, then Mercurial has supported repositories with multiple branches since..., always I think. Git repositories with multiple branches are exactly that: multiple diverged strands of development in a single repository. Git then adds names to these strands and allow you to query these names remotely. The Bookmarks extension for Mercurial adds local names, and with Mercurial 1.6, you can move these bookmarks around when you push/pull..
I use Linux, but apparently TortoiseHg is faster and better than the Git equivalent on Windows (due to better usage of the poor Windows filesystem). Both http://github.com and http://bitbucket.org provide online hosting, the service at Bitbucket is great and responsive (I haven't tried github).
I chose Mercurial since it feels clean and elegant -- I was put off by the shell/Perl/Ruby scripts I got with Git. Try taking a peek at the git-instaweb.sh file if you want to know what I mean: it is a shell script which generates a Ruby script, which I think runs a webserver. The shell script generates another shell script to launch the first Ruby script. There is also a bit of Perl, for good measure.
I like the blog post that compares Mercurial and Git with James Bond and MacGyver -- Mercurial is somehow more low-key than Git. It seems to me, that people using Mercurial are not so easily impressed. This is reflected in how each system do what Linus described as "the coolest merge EVER!". In Git you can merge with an unrelated repository by doing:
git fetch <project-to-union-merge>
GIT_INDEX_FILE=.git/tmp-index git-read-tree FETCH_HEAD
GIT_INDEX_FILE=.git/tmp-index git-checkout-cache -a -u
git-update-cache --add -- (GIT_INDEX_FILE=.git/tmp-index git-ls-files)
cp .git/FETCH_HEAD .git/MERGE_HEAD
git commit
Those commands look quite arcane to my eye. In Mercurial we do:
hg pull --force <project-to-union-merge>
hg merge
hg commit
Notice how the Mercurial commands are plain and not special at all -- the only unusual thing is the --force flag to hg pull, which is needed since Mercurial will abort otherwise when you pull from an unrelated repository. It is differences like this that makes Mercurial seem more elegant to me.