O Linux Mint Debian Edition vem por padrão com duas interfaces gráficas o Mate, que é um fork do Gnome 2, e o Cinnamon que é um fork do Gnome 3 que o modifica para ficar mais parecido com a versão 2 do Gnome. Portanto, não importa se você usa o Mate ou o Cinnamon você está usando Gnome.

Caso você instale um programa e o mesmo não apareça nos menus do Gnome você pode criar um arquivo .desktop fazendo com que o sistema o reconheça automaticamente.

A forma mais simples de criar um arquivo desktop é copiando de outro arquivo e alterando o que interessa mas se você quiser conhecer mais algumas informações sobre o arquivo e parâmetros possíveis eu recomendo estes links:

http://developer.gnome.org/integration-guide/stable/desktop-files.html.pt_BR

http://standards.freedesktop.org/menu-spec/latest/apa.html

http://www.nautilus-actions.org/?q=node/377

Para essa demonstração vou criar um arquivo .desktop para o Google Chrome. Quero que o Chrome entre no menu Internet igual ao Firefox e por isso vou usá-lo como base.

$ sudo cp /usr/share/applications/firefox.desktop /usr/share/applications/google-chrome.desktop
$ sudo pluma /usr/share/applications/google-chrome.desktop

O arquivo original estava assim:

[Desktop Entry]
Version=1.0
Name=Firefox Web Browser
Name[ar]=متصفح الوِب فَيَرفُكْس
Name[ca]=Navegador web Firefox
Name[cs]=Firefox Webový prohlížeč
Name[es]=Navegador web Firefox
Name[et]=Firefoxi veebibrauser
Name[fa]=مرورگر اینترنتی Firefox
Name[fi]=Firefox-selain
Name[fr]=Navigateur Web Firefox
Name[hu]=Firefox webböngésző
Name[it]=Firefox Browser Web
Name[ja]=Firefox ウェブ・ブラウザ
Name[ko]=Firefox 웹 브라우저
Name[nb]=Firefox Nettleser
Name[nl]=Firefox webbrowser
Name[nn]=Firefox Nettlesar
Name[no]=Firefox Nettleser
Name=Przeglądarka WWW Firefox
Name[pt]=Firefox Navegador Web
Name[pt_BR]=Navegador Web Firefox
Name[sk]=Firefox - internetový prehliadač
Name[sv]=Webbläsaren Firefox
Comment=Browse the World Wide Web
Comment[ar]=تصفح الشبكة العنكبوتية العالمية
Comment[ca]=Navegueu per el web
Comment[cs]=Prohlížení stránek World Wide Webu
Comment[de]=Im Internet surfen
Comment[es]=Navegue por la web
Comment[et]=Lehitse veebi
Comment[fa]=صفحات شبکه جهانی اینترنت را مرور نمایید
Comment[fi]=Selaa Internetin WWW-sivuja
Comment[fr]=Navigue sur Internet
Comment[hu]=A világháló böngészése
Comment[it]=Esplora il web
Comment[ja]=ウェブを閲覧します
Comment[ko]=웹을 돌아 다닙니다
Comment[nb]=Surf på nettet
Comment[nl]=Verken het internet
Comment[nn]=Surf på nettet
Comment[no]=Surf på nettet
Comment=Przeglądanie stron WWW 
Comment[pt]=Navegue na Internet
Comment[pt_BR]=Navegue na Internet
Comment[sk]=Prehliadanie internetu
Comment[sv]=Surfa på webben
GenericName=Web Browser
GenericName[ar]=متصفح وب
GenericName[ca]=Navegador web
GenericName[cs]=Webový prohlížeč
GenericName[es]=Navegador web
GenericName[et]=Veebibrauser
GenericName[fa]=مرورگر اینترنتی
GenericName[fi]=WWW-selain
GenericName[fr]=Navigateur Web
GenericName[hu]=Webböngésző
GenericName[it]=Browser Web
GenericName[ja]=ウェブ・ブラウザ
GenericName[ko]=웹 브라우저
GenericName[nb]=Nettleser
GenericName[nl]=Webbrowser
GenericName[nn]=Nettlesar
GenericName[no]=Nettleser
GenericName=Przeglądarka WWW
GenericName[pt]=Navegador Web
GenericName[pt_BR]=Navegador Web
GenericName[sk]=Internetový prehliadač
GenericName[sv]=Webbläsare
Exec=/opt/firefox/firefox %u
Terminal=false
X-MultipleArgs=false
Type=Application
Icon=/opt/firefox/icons/mozicon128.png
Categories=Application;Internet;Network;WebBrowser;
MimeType=text/html;text/xml;application/xhtml+xml;application/xml;application/vnd.mozilla.xul+xml;application/rss+xml;application/rdf+xml;image/gif;image/jpeg;image/png;
StartupWMClass=Firefox
StartupNotify=true

Após a edição ele ficou assim:

[Desktop Entry]
Version=1.0
Name=Google Chrome
Name[pt_BR]=Navegador Web Google Chrome
Comment=Browse the World Wide Web
Comment[pt_BR]=Navegue na Internet
GenericName=Web Browser
GenericName[pt_BR]=Navegador Web
Exec=/opt/google/chrome %u
Terminal=false
X-MultipleArgs=false
Type=Application
Icon=/opt/google/chrome/product_logo_256.png
Categories=Application;Internet;Network;WebBrowser;
MimeType=text/html;text/xml;application/xhtml+xml;application/xml;application/vnd.mozilla.xul+xml;application/rss+xml;application/rdf+xml;image/gif;image/jpeg;image/png;
StartupWMClass=Chrome
StartupNotify=true

As alterações mais importantes são:

Name => Nome do Aplicativo
Exec => Path para o executável (o %u é específico para o browser abrir uma url passada como parâmetro).
Icon => Path para o ícone (pode ser jpg, png, svg ou até o próprio executável do programa).
Categories = > Menu onde o atalho para o programa vai aparecer.

Você pode sempre usar outros arquivos .desktop como base para a criação do seu.

Veja também como colocar seu programa no path neste artigo.

Espero ter ajudado!