Mercurial also talks with git (http://hg-git.github.com/) so you can use it with github if you want. This was actually created by Scott Chacon, the guy who wrote the subject of the OP.

I think it's worth giving both git and hg a try to see which fits your head better. Mercurial feels better to me and there are quite a few people in many communities (including most of the python community).