This package solely ships "notify-send", but doesn't mention it in the
package description, so "apt-cache search notify send" doesn't find
it.

Please consider mentioning it, perhaps like this:

Description-en: sends desktop notifications to a notification daemon (Utilities)
 A library that sends desktop notifications to a notification daemon, as
 defined in the Desktop Notifications spec. These notifications can be
 used to inform the user about an event or display some form of
 information without getting in the user's way.
 .
 This package contains the notify-send command line utility.

Thanks,
Christoph