No sistema operacional elementar e em outras distribuições baseadas no Debian, como Ubuntu e Linux Mint, o pacote é libnotify-dev . Geralmente, para compilar um programa que usa a biblioteca XXX, você precisa do pacote chamado libXXX-dev .
Você pode iniciar um terminal, efetuar login como root (ou, caso não haja uma conta root, usar sudo -s ) e executar:
apt-get update
apt-get install -y libnotify-dev
Mas há outras maneiras de instalar um pacote também.