Update for Ubuntu 18.04

At the date Ubuntu 18.04 was released Nautilus-Actions was/is no longer available. It also seems to have been superseded by a new program, called Filemanager-Actions, which otherwise looks identical.

To install this program, see this solution.

Nautilus Actions

We may define our own right-click context menu items with nautilus-actions .

• Run the Nautilus-Actions Configuration Tool either from the Dash, or from a terminal with

   nautilus-actions-config-tool
  

• In the Action tab give your action a sensible label, e.g. "Open in Terminator" and choose to display this in the selection or the context menu.

• Next open the Command tab to enter the commands to run

• Give in the full path to your command (/usr/bin/command_to_run) and program options.

• After logging out and in again the right click context menu below will be displayed:

This answer is outdated: a recently updated answer is this one.

App developers wanting to add their app's actions — see this page below, here and here.

Context menus of Nautilus used to be customizable by Nautilus extensions. Be warned that this link leads to archived doc; Gnome devs removed that documentation and no longer support that kind of customization. It may still work though.

You can also place plain shell scripts under the ~/.local/share/nautilus/scripts (~/.gnome2/nautilus-scripts in early releases) directory, and they will appear in file context menu under Scripts submenu.

One can Use python-nautilus extension as an alternative to nautilus-actions.

To install:

sudo apt-get install python-nautilus

A simple example:

import os

from gi.repository import Nautilus, GObject

class ColumnExtension(GObject.GObject, Nautilus.MenuProvider):
    def __init__(self):
        pass
    def menu_activate_cb(self, menu, file):
         os.system("write here your simple bash command & pid=$!")

    def get_background_items(self, window, file):
        item = Nautilus.MenuItem(name='ExampleMenuProvider::Foo2', 
                                         label='Name of your item', 
                                         tip='',
                                         icon='')
        item.connect('activate', self.menu_activate_cb, file)
        return item,

Copy this python script under ~/.local/share/nautilus-python/extensions and restart nautilus. When you right click on the desktop and select your item, your simple bash command will be executed :)

November 29, 2016 era Ubuntu 14.04, 16.04 and 16.10 plus earlier versions.

See Nautilus instructions for creating your own script here (Help Ubuntu - Nautilus Scripts How to). Basically you:

• Navigate to the directory ~/.local/share/nautilus/scripts/
• Place your script (written in Bash, Perl or Python) there.
• Mark the script as executable using Nautilus or from terminal with chmod +x script_name
• Nautilus makes environmental variables available to your script: NAUTILUS_SCRIPT_SELECTED_FILE_PATHS, NAUTILUS_SCRIPT_SELECTED_URIS, NAUTILUS_SCRIPT_CURRENT_URI, and NAUTILUS_SCRIPT_WINDOW_GEOMETRY

There are sample scripts located at (Help Ubuntu - Nautilus Sample Scripts) for e-mailing files, mounting an ISO file, setting files to read only, editing file with gedit ROOT priviledges, opening terminal at current location, etc.

Look through the scripts and take one as a template for encrypting files, uploading to the cloud, compressing to backup or whatever you need to do.

If you want to be able to do something at any time, do like ulidtko says and use ~/.gnome2/nautilus-scripts.

If you want to be able to customize when you see it, install the nautilus-actions package, then go to System->Preferences->Nautilus Actions Configuration.

TL;DR

The best solution for app developers is to use python-nautilus.

Create your python script (following examples and bad documentation) and copy it to the correct folder:

mkdir -p ~/.local/share/nautilus-python/extensions && cp script.py ~/.local/share/nautilus-python/extensions

Detailed Explanation

Let's say you want to create an application that the user installs with a script or a .deb file, with that in mind I'll be explaining why I think python-nautilus is a better solution compared with nautilus-actions and the nautilus scripts.

Nautilus Actions

This is the only solution to offer a GUI and therefore makes it easy to create complex behavior, for example decide what menu entries to show if the selected file's mime-type is text/plain.

The main problem with this solution is that it is not easy (if even possible) to import the entries to another computer without the Configuration Tool and the user importing it, let's just say it would not be possible to do with a script.

Nautilus Scripts

This is the more straight forward solution, pick up a script, place it in a folder and done. This would definitely allow a install script or a .deb file to create a new entry in the context menu. What are the problems? Where do I start...

• It always appears under a Scripts sub-menu.
• It doesn't show if you have nothing selected.
• It doesn't allow you to decide if you should show the entry or not.
• Does not allow Tooltips or different Titles. (maybe I'm being picky)

A good app doesn't use shortcuts like this, because it ruins the user experience.

python-nautilus

Not as easy to create as the previous solutions, but offers the best of both worlds. Scripting and customization.

This solution allows you to create a python script that receives the files selected in nautilus and let's you decide if you wish to show a entry or not and what to do with that entry. It also allows you to create sub-menus and or cool stuff.

The drawback is the big lack of documentation and developers that just want to add an entry may find themselves losing a couple of hours to create a working prototype (In my research I found a solution based on C that was way more complicated than this).

I normally use Visual Studio Code, while on Windows it offers a context menu entry Open with Visual Studio Code, it's lacking the same functionality on Linux, with the Python solution it would be easy to solve the problem. I think may apps in Linux could benefit from having a nautilus integration.

Hope this explanation helped you decide what to choose.