Você pode encontrar pacotes nagios3 com o comando:
aptitude search nagios3
Ou apenas:
aptitude search nagios
Para instalá-lo, execute:
aptitude install nagios3 nagios-plugins nagios-plugins-basic nagios-plugins-standard nagios-plugins-extra