This is specified in an application's desktop entry file. Desktop entry files are launchers for the application (the same file format as the launchers you can create on your desktop) which also contain various metadata. When an application is installed these desktop entry files are placed in /usr/share/applications and I think their contents is also cached to improve speed.
The important piece of data defined here is list of MIME types that the application can open. This is defined in the 'MimeType' key in the desktop entry file. For example, GIMP has the following in its desktop entry:
This specifies a list of file types that GIMP can open.
The application name is specified with the 'Name' key, eg.
Name=GIMP Image Editor
As you can see, there are icons next to the names. These are also specified in the desktop entry file as either an icon name (for which the correct file is looked up from the icon theme) or an icon file path. GIMP has the following:
In the 'Open with -> Other application' dialog, the Recommended Applications are the applications which specify that they are able to open the file type and the Other Applications are those which haven't.
When you have chosen the application, the file manager looks up how to run the application to open the file(s). It looks for the 'Exec' key in the desktop entry. GIMP has the following Exec key:
This means that the command:
will be run to open the file(s) with
%U replaced with a list of URLs (normally file:// urls) representing the files that have been selected for opening. In addition to '%U', the application may use '%u' for a single url or '%f'/'%F' for a single/multiple file path(s).