Na minha instalação do Kubuntu 15.10 e do KDE neon, o comando notify-send
não estava disponível até que eu instalei o pacote libnotify-bin .
Depois de instalar o libnotify-bin , o notify-send
funciona bem:
sudo apt-get install libnotify-bin