A package should provide a menu file /usr/lib/menu/<package-name> that contains information about each program it likes to make available in the menus.
You should add a line like this to your postinst script
if test -x /usr/bin/update-menus; then update-menus; fi
and the postrm script should get the line
if test -x /usr/bin/update-menus; then update-menus; fi
(that is, the same line in postinst and in postrm).
Debian Menu System
version 1.4, 22 March 2005joostje@debian.org
joeyh@debian.org
schwarz@debian.org
ballombe@debian.org