Você precisa da biblioteca de desenvolvimento libpython-dev
:
sudo apt-get install libpython-dev
Atualmente, o comando instala libpython2.7-dev
$ apt-file search /Python.h
[..]
libpython2.7-dbg: /usr/include/python2.7_d/Python.h
libpython2.7-dev: /usr/include/python2.7/Python.h
libpython3.4-dbg: /usr/include/python3.4dm/Python.h
libpython3.4-dev: /usr/include/python3.4m/Python.h
[..]