Notify-osd je v repu sida i sqeeze, po instalaci můžeš zkontrolovat funkčnost spuštěním
notification-properties
Jak se k tomu staví další aplikace v už je věc jiná, takovou podporu, jako v Ubuntu asi čekat nelze.
Zkoušel jsem ve squeeze třeba Rhythmbox a funguje to jako v Ubuntu.