Building Mercurial (hg) -- fatal error: Python.h: No such file or directory

The version of Mercurial you get using sudo apt-get install mercurial is a relatively old one. But, if you download it from http://mercurial.selenic.com/, you can get the latest. However, in a fresh install of Linux Mint, I got the following error when I tried to run sudo make install:

mercurial/base85.c:13:20: fatal error: Python.h: No such file or directory
compilation terminated.

To fix this, you need to install the python-dev package using:

sudo apt-get install python-dev

You'll need to install python-docutils, too. Then you can run make install.