PostgreSQL é dividido em vários pacotes, e tendo
psql instalado não implica que os pacotes de desenvolvimento também estejam instalados. De acordo com a mensagem de erro:
você precisa:
# apt-get install postgresql-server-dev-9.1
Observe também que há um repositório APT pgdg fornecendo versões pré-compiladas recentes de pacotes relacionados ao postgres (incluindo postgis) que você pode usar em vez de auto-compilar.
Se o seu sistema estiver configurado para usar este repositório, faça:
# apt-get install postgresql-9.1-postgis-2.0
