Para poder ejecutar script desde nautilus tenemos que tener instalado el paquete python-nautilus que viene en los repositorios de cualquier distro actual o empaquetado en RPM. A continuación descomprime el paquete de scripts (bájalo desde aquí o desde el botón que está en el menú de la derecha). Luego sólo tendremos que copiar los scripts en el directorio:

/home/usuario/.gnome2/nautilus-scripts

Una vez hecho esto si seleccionamos desde nautilus cualquier archivo y pulsamos el botón derecho aparecerá un menú llamado "Scripts" con la misma estructura que el directorio anterior y podremos ejecutarlos.

Asegúrate que los scripts tienen permisos de ejecución.