Вы можете использовать nautilus-действия из командной строки и скрипта:
man nautilus-actions-new
Однако для этого требуется, чтобы этот пакет был установлен (я использую Ubuntu Oneiric Alpha, и этот пакет не был установлен), чего можно добиться только путем упаковки вашей программы в качестве архива deb.
Другая возможность Сценарии Nautilus , которая не требует никаких пакетов. Но это поместит ваш пункт меню в подменю.
Такие программы, как nautilus-open-Terminal добавляют вещи в меню Nautilus без каких-либо зависимостей, вы можете проверить его источник.