Existe um script nautilus para isso. Aqui estão os comandos:
wget http://dl.dropbox.com/u/47950494/Create-Launcher
cp Create-Launcher ~/.gnome2/nautilus-scripts
chmod +x ~/.gnome2/nautilus-scripts/Create-Launcher
mv ~/.gnome2/nautilus-scripts/Create-Launcher 'home/[your user name here]/.gnome2/nautilus-scripts/Create Launcher'
O quarto comando é apenas para renomear o arquivo, você pode fazer isso no Nautilus também. Aproveite!
Fonte: aqui