Na verdade, é bem simples. Os itens de menu são preenchidos com as entradas .desktop em /usr/share/applications" and "$HOME/.local/share locations. Você pode criar arquivos .desktop personalizados e colocá-los em um desses locais. Isso começará a aparecer na área de trabalho do Gnome com outros aplicativos.
Para mais informações sobre como criar arquivos .desktop, dê uma olhada nisso:
http://library.gnome.org/admin/system-admin-guide/stable/menustructure-desktopentry.html.en