Primeiro, verifique a versão no Nautilus:
nautilus --version
- Se a versão 3.6 ou superior for para a pasta:
~/.local/share/nautilus/scripts
- Senão, vá para
~/.gnome2/nautilus-scripts
Agora você deve poder colocar um script nessa pasta. Isso funciona para bash (clique direito e há uma opção chamada scripts), acho que funciona para python também. Se o script python não aparecer, talvez seja necessário criar um script bash para chamar o python. Lembre-se de tornar seu script executável! Também confira este link para mais informações (como variáveis nautilus define quando seus scripts de execução são clicados com o botão direito, como a pasta ou o arquivo em que você clicou).