How does Linux choose which application to open a file?

There may be different mecanisms to handle these default settings. However, other answers tend to focus on complete desktop environments, each of them with its own mecanism. Yet, these are not always installed on a system (I use OpenBox a lot), and in this case, tools such as xdg-open may be used.

Quoting the Arch Wiki:

xdg-open is a desktop-independent tool for configuring the default applications of a user. Many applications invoke the xdg-open command internally.

At this moment, I am using Ubuntu (12.04) and xdg-open is available. However, when you use a complete desktop environment such as GNOME, xdg-open acts as a simple forwarder, and relays the file requests to your DE, which is then free to handle it as it wants (see other answers for GNOME and Nautilus, for instance).

Inside a desktop environment (e.g. GNOME, KDE, or Xfce), xdg-open simply passes the arguments to that desktop environment's file-opener application (gvfs-open, kde-open, or exo-open, respectively), which means that the associations are left up to the desktop environment.

... which brings you back to the other answers in that case. Still, since this is Unix & Linux, and not Ask Ubuntu:

When no desktop environment is detected (for example when one runs a standalone window manager, e.g. Openbox), xdg-open will use its own configuration files.

All in all:

                            |-- no desktop env. > handle directly.
User Request > xdg-open > --|
                            |-- desktop env.    > pass information to the DE.

If the first case, you'll need to configure xdg-open directly, using the xdg-mime command (which will also allow you to see which application is supposed to handle which file). In the second case...

                        |-- GNOME? > gvfs-open handles the request.
                        |
Info. from xdg-open > --|-- KDE?   > kde-open handles the request.
                        |
                        |-- XFCE?  > exo-open handles the request.

... you'll need to configure the file-opener associated with your desktop environment. In some cases, configuration made through xdg-mime may be redirected to the proper configuration tool in your environment.

From the wiki entry,

Linux-based GUIs, such as KDE and GNOME, support MIME type-based associations. For example, the MIME type text/plain would be associated with a text editor.

Also, this answer has more details.

File manager often use some combination of option a and b (e.g. look at the file extension first, if it's not known (or the file does not have an extension), look at the contents).

A file's type is not stored as metadata on common linux file systems.

From this answer, I see the below information.

The file manager (Nautilus, by default) uses the MIME type of a file to determine which program to open it with. When an application is installed, it can specify what MIME types it can open and the command to use to open the files in the .desktop file which is placed in /usr/share/applications. This is the file used for menus, desktop shortcuts, etc.

A file doesn't tell the OS its file format, with one exception:

If an executable file starts with a so-called shebang line, like

#! /usr/bin/perl

then this line tells the Linux kernel that it should be started with /usr/bin/perl (that is, instead of executing this file, it should execute usr/bin/perl and give this file as argument). This of course only works with file formats which ignore (or understand) such a shebang line.

Other than that, the operating system as such knows nothing about file types. However many programs which allow opening other files have their own mechanism to decide which program to use for opening which file. That can be a list inside the program itself (Firefox for example maintains such a list), or the program can delegate it to the desktop environment (of which there are several for Linux).

Usually, those mechanisms only consider the filename to decide what type the file is; an exception are email clients and web browsers, where usually the type of the file is explicitly given by the server/stated in the mail.

The mechanism is usually two-step:

• First, from the file name or supplied information, determine the MIME type of the file (the MIME type is a standardized, but extensible list of file types).
• Second, from the MIME type, determine which program to execute, usually through a sort of registry maintained either by the program itself or by the desktop environment the program was written for.

It is done similar to MS-Windows.

It is not done by OS. It is done by file manager, a part of the windowing system. Usually the part of the file-name after the last dot . is used to make the decision. There is a way to set them in settings, or when you right click on a file.

So the file does not tell the OS, the file is not active so can do nothing on its own, but the file manager looks at the file-name, the file manager could also look inside the file much as the file utility does.

As @richard says, it's similar to Windows. A generic file manager may look at the name of a file first and try to recognize a file extension which is associated with a program. If that fails, it may try to open the file and look for a header. If you try to read a non-text file (say, a .jpeg), you'll see a string of data which describes the file. For instance, this is the first line of a .jpeg which I had lying around:

'\xff\xd8\xff\xe0\x00\x10JFIF\x00\x01\x01\x00\x00\x01\x00\x01\x00\x00\xff\xfe\x00;CREATOR: gd-jpeg v1.0 (using IJG JPEG v80), quality = 90'