Прежде всего, заголовочный файл для встраивания или расширения python - Python.h
, с прописными буквами P. Linux чувствителен к регистру, и python.h не будет работать.
В производных от Debian и Debian, таких как Ubuntu, вы можете использовать apt-file, чтобы узнать, какой пакет установить, с указанием имени файла:
$ apt-file search Python.h
...
python2.6-dbg: /usr/include/python2.6_d/Python.h
python2.6-dev: /usr/include/python2.6/Python.h
...