Do you have package
python-dev installed? That's where Python.h comes from.
These are the steps to find this information out for yourself:
apt-file search Python.h to find all packages that provide files that have
Python.h in their name (You might have to install apt-file first). This lists a lot of packages, but most provide files like
Symbol-Tables-In-Python.html. The only packages that provide a Python.h file are pythonX.X-dbg and pythonX.X-dev packages. Now, -dbg packages contain debug version of programs, while -dev contain development files such as C header files, and Python.h is such a file.
This narrows the list of packages down to python2.6-dev, python2.7-dev, and python3.2-dev. One way to check which of these version is the canonical one is to simple remove the version number from the package name, and check if this exists:
apt-cache show python-dev:
Maintainer: Ubuntu Developers <email@example.com>
Original-Maintainer: Matthias Klose <firstname.lastname@example.org>
Depends: python (= 2.7.2-7ubuntu2), python2.7-dev (>= 2.7.2-3~)
Description-en: header files and a static library for Python (default)
Header files, a static library and development tools for building
Python modules, extending the Python interpreter or embedding Python
This package is a dependency package, which depends on Debian's default
Python version (currently v2.7).
Depends: line shows that it will install python2.7-dev, so you can just install python-dev.
Since I already had the correct packages installed, I could use
locate Python.h and then
dpkg -S /usr/include/python2.7/Python.h to find the package that contains Python.h.