Basic questions in Majorana fermions Why any fermion can be written as a combination of two Majorana fermions? Is there any physical meaning in it? Why Majorana fermion can be used for topological quantum computation?
 A: I put an extra answer, since I believe the first Jeremy's question is still unanswered. The previous answer is clear, pedagogical and correct. The discussion is really interesting, too. Thanks to Nanophys and Heidar for this.
To answer directly Jeremy's question: you can ALWAYS construct a representation of your favorite fermions modes in term of Majorana's modes. I'm using the convention "modes" since I'm a condensed matter physicist. I never work with particles, only with quasi-particles. Perhaps better to talk about mode.
So the unitary transformation from fermion modes created by $c^{\dagger}$ and destroyed by the operator $c$ to Majorana modes is 
$$
c=\dfrac{\gamma_{1}+\mathbf{i}\gamma_{2}}{\sqrt{2}}\;\text{and}\;c{}^{\dagger}=\dfrac{\gamma_{1}-\mathbf{i}\gamma_{2}}{\sqrt{2}}
$$
or equivalently 
$$
\gamma_{1}=\dfrac{c+c{}^{\dagger}}{\sqrt{2}}\;\text{and}\;\gamma_{2}=\dfrac{c-c{}^{\dagger}}{\mathbf{i}\sqrt{2}}
$$
and this transformation is always allowed, being unitary. Having doing
this, you just changed the basis of your Hamiltonian. The quasi-particles
associated with the $\gamma_{i}$'s modes verify $\gamma{}_{i}^{\dagger}=\gamma_{i}$,
a fermionic anticommutation relation $\left\{ \gamma_{i},\gamma_{j}\right\} =\delta_{ij}$,
but they are not particle at all. A simple way to see this is to try
to construct a number operator with them (if we can not count the
particles, are they particles ? I guess no.). We would guess $\gamma{}^{\dagger}\gamma$
is a good one. This is not true, since $\gamma{}^{\dagger}\gamma=\gamma^{2}=1$
is always $1$... The only correct number operator is $c{}^{\dagger}c=\left(1-\mathbf{i}\gamma_{1}\gamma_{2}\right)$.
To verify that the Majorana modes are anyons, you should braid them
(know their exchange statistic) -- I do not want to say much about
that, Heidar made all the interesting remarks about this point. I
will come back later to the fact that there are always $2$ Majorana
modes associated to $1$ fermionic ($c{}^{\dagger}c$) one. Most has
been already said by Nanophys, except an important point I will discuss
later, when discussing the delocalization of the Majorana mode. I
would like to finnish this paragraph saying that the Majorana construction
is no more than the usual construction for boson: $x=\left(a+a{}^{\dagger}\right)/\sqrt{2}$
and $p=\left(a-a{}^{\dagger}\right)/\mathbf{i}\sqrt{2}$: only $x^{2}+p^{2} \propto a^{\dagger} a$
(with proper dimension constants) is an excitation number. Majorana
modes share a lot of properties with the $p$ and $x$ representation
of quantum mechanics (simplectic structure among other).
The next question is the following: are there some situations when
the $\gamma_{1}$ and $\gamma_{2}$ are the natural excitations of
the system ? Well, the answer is complicated, both yes and no. 


*

*Yes, because Majorana operators describe the correct excitations of
some topological condensed matter realisation, like the $p$-wave
superconductivity (among a lot of others, but let me concentrate on this specific one, that I know better). 

*No, because these modes are not excitation at all ! They are zero
energy modes, which is not the definition of an excitation. Indeed,
they describe the different possible vacuum realisations of an emergent
vacuum (emergent in the sense that superconductivity is not a natural
situation, it's a condensate of interacting electrons (say)). 


As pointed out in the discussion associated to the previous answer,
the normal terminology for these pseudo-excitations are zero-energy-mode.
That's what their are: energy mode at zero-energy, in the middle of
the (superconducting) gap. Note also that in condensed matter, the
gap provides the entire protection of the Majorana-mode, there is
no other protection in a sense. Some people believe there is a kind
of delocalization of the Majorana, which is true (I will come to that
in a moment). But the delocalization comes along with the gap in fact:
there is not allowed propagation below the gap energy. So the Majorana
mode are necessarilly localized because they lie at zero energy, in
the middle of the gap. 
More words about the delocalization now -- as I promised. Because
one needs two Majorana modes $\gamma_{1}$ and $\gamma_{2}$ to each
regular fermionic $c{}^{\dagger}c$ one, any two associated Majorana
modes combine to create a regular fermion. So the most important challenge
is to find delocalized Majorana modes ! That's the famous
Kitaev proposal arXiv:cond-mat/0010440 -- he said unpaired Majorana instead of delocalised, since delocalization comes for free once again. At the
end of a topological wire (for me, a $p$-wave superconducting wire)
there will be two zero-energy modes, exponentially decaying in space
since they lie at the middle of the gap. These zero-energy modes can
be written as $\gamma_{1}$ and $\gamma_{2}$ and they verify $\gamma{}_{i}^{\dagger}=\gamma_{i}$
each !
To conclude, an actual vivid question, still open: there are a lot
of pseudo-excitations at zero-energy (in the middle of the gap). The
only difference between Majorana modes and the other pseudo-excitations
is the definition of the Majorana $\gamma^{\dagger}=\gamma$, the
other ones are regular fermions. How to detect for sure the Majorana
pseudo-excitation (zero-energy mode) in the jungle of the other ones
?
A: Majorana fermions are fermions which are their own antiparticles. As a result, they only have half the degrees of freedom as a regular Dirac electron. One physical interpretation, at least for Majorana fermion quasiparticles in condensed matter systems, is that they can be thought of a superposition of an electron and hole state.
Only Majorana bound states can be used to do topological quantum computation. If you have a system with $2N$ well-separated Majorana fermions then you have a $2^N$-fold degenerate ground state. You can perform quantum computation on this system by performing a sequence of exchanges between these $2N$ Majorana fermions. These exchanges are known as "braiding" operations. Additionally, the order in which you perform the braiding operations matters. Hence the system is said to possess nonabelian statistics.
It is important to understand what it means to do a computation. Since Majoranas are sort of like half-fermions we can't really measure them directly. We can infer their existence. Another way to  understand the trouble with measuring a Majorana fermion is an ambiguity in its unique identification! Say we have a system with $2N$ Majorana fermions and consequently $N$ regular fermions. You need to pair up two Majoranas to get a regular fermion (which we can measure). But there are more than one ways of doing this! You can do this in $$\frac{(2N)!}{2!(2N-2)!}$$ number of ways. Say we agree on a convention and decide to pair up or fuse two Majoranas in a certain way. For example, in a 1-D lattice we decide to only pair up nearest-neighbor Majoranas. This, in fact, is the best choice of pairing them. So now you do a bunch of braiding operations and in the end fuse the Majoranas according to the agreed convention and then measured the resulting regular fermion states. That's when we have done the computation. Just exchanging them is not enough. You won't able to tell if they were actually exchanged without fusing them! You can read more on this in section 3 of this excellent review article:
http://arxiv.org/abs/1206.1736
Finally, I'll comment on what this whole "topological" business is. One of the most fascinating and counterintuitive property of a system containing Majoranas is that you can have nonlocal states in your system. As I mentioned above, you can pretty much fuse any two Majoranas to get a regular electron. It doesn't matter if those two Majorana fermions are spatially far apart. The resulting (regular) electronic state by the fusion of these two Majoranas is highly nonlocal. The fact that this electronic state is nonlocal means that any local perturbations cannot destroy this state. Hence such systems are immune to decoherence which is one of the biggest problems faced by other quantum computation schemes. This is one of the biggest appeals of topological quantum computation.
There is, however, one catch to this interesting story. You cannot perform universal quantum computation with Majorana fermions. Two additional processes are necessary for that: the $\pi/8$ phase gate and a way to read the eigenvalue of the product of 4 Majorana operators without measuring the eigenvalues of individual pairs (in that group of 4). Unfortunately current ways implementing such processes do not enjoy topological protection. But still some topological protection is better than none!
