Имеем структуру папок для deb-пакета:
SoftwareName/DEBIAN (файлы control, postinstall и т.д.)
SoftwareName/opt (наша папка с бинарником и пр доп файлами)
SoftwareName/usr и в ней папки bin и share.
В первой там файл/скрипт запуска, например, а вот в share две папки: applications и menu.
В applications файлик создаем SoftwareName.desktop с содержимым:
[Desktop Entry]
Type=Application
Encoding=UTF-8
Name=SoftwareName
Comment=Запуск SoftwareName
Exec=/usr/bin/имя к файлу запуска
Icon=/opt/my-software/product_logo_48.png
Terminal=false
GenericName[en_US]=SoftwareName
В папке menu создаем файл SoftwareName.mune с содержимым:
?package(название бинарника запуска):needs="x11" \
section="Applications/Network/Web Browsing" \
hints="Web browsers" \
title="SoftwareName" \
icon="/opt/my-software/product_logo_32.xpm" \
command="/usr/bin/softwarename"
Делал на примере deb-пакета Хрома для Убунты.