Então, você precisa do bit PHP para se conectar ao mongo.
Você pode usar o PECL para instalá-lo executando algo como pecl install mongo
.
Você também pode instalá-lo mais manualmente acessando o link
Eu não acredito que o Ubuntu (pelo menos 10.04) tenha um pacote PHP-mongo, pelo menos não de acordo com aptitude search mongo
.
Atualização:
Como mencionado abaixo, o OP precisava do pacote build-essential, que incluiria coisas como make, gcc, etc. link