Você precisa instalar o pacote php5-cli
ou php5-cgi
.
sudo apt-get install php5-cli
# OR
sudo apt-get install php5-cgi
Como Zoredache observou no comentário. A versão cli não processa cabeçalhos nem os fornece - é uma espécie de interpretador PHP limpo e completamente inconsciente de HTTP.
Se você quiser uma versão capaz de ser mencionada acima, use a versão CGI.