Você precisa instalar os pacotes *-dev
se quiser compilar algo em uma biblioteca.
No seu caso, seria um ou mais destes:
$ apt-cache search libnotify dev
libnotify-cil-dev - CLI library for desktop notifications
libnotifymm-dev - C++ binding for libnotify (development files)
libnotify-dev - sends desktop notifications to a notification daemon
Eu tenho o Ubuntu 10.04, seus resultados podem variar.