Pois bem, a instalação do MongoDB pra quem já tentou é um pouco chata e complicada no primeiro momento. Alguns erros ocorrem dificultando a instalação e podem desistimular alguns desenvolvedores a usarem.
Montei uma VM Ubuntu com Vagrant para ter histórico de todos os comandos necessários, então para começar abra o terminal e siga os passos abaixo:
1) Importe a chave(GPG key) 10gen, necessária para pacotes Ubuntu: