Con Gambas3 puoi con il 2 non mi sembra, comunque è sufficiente controllare la presenza di tale libreria
dpkg -l | grep libnotify-bin
se ti viene restituito l'output è presente altrimenti no e quindi deve essere installata.
Nel dubbio metterei semplicemente in "testa" al programma un bel comando "gksu apt-get install libnotify-bin" specificando ovviamente all'utente che non gli vai ad installare nulla di anomalo.
In alternativa dopo che hai creato il deb del progetto lo riapri e metti il pacchetto come dipendenza a mano.
Vedi tu come preferisci procedere.