What does it mean by complex frequencies? (Quasinormal Modes) Something I've taken for granted and not yet thought about physically, is how the frequency of quasinormal modes related to a black hole are $\textit{complex}$.
I know that it's something to do with the fact that these modes decay but I tried to explain it to myself with several different reasonings, none of them convincing enough for me to move on. 
Wikipedia says:
"... $\mathbf{\omega}$ is what is commonly referred to as the quasinormal mode frequency. It is a complex number with two pieces of information: real part is the temporal oscillation; imaginary part is the temporal, exponential decay"
but I'm afraid I can't grasp this statement fully and an explanation would be great. Is it something to do with satisfying the wave equation?
 A: 
This still doesn't explain to what the importance of the factor of i
  is

Euler's formula
$$e^{i\omega} = \cos \omega + i\sin \omega$$
Thus, the real part of $e^{i\omega}$ is $\cos \omega$: 
$$\cos \omega = \frac{e^{i\omega} + e^{-i\omega}}{2}$$
and the imaginary part of $e^{i\omega}$ is $\sin \omega$: 
$$\sin \omega = \frac{e^{i\omega} - e^{-i\omega}}{2i}$$
Now consider the complex number
$$s = i\sigma + \omega$$
which we will call the complex frequency.
By the above, we have
$$e^{ist} =  e^{-\sigma t}e^{i\omega t} = e^{-\sigma t}\left(\cos \omega t + i\sin \omega t\right)$$
The real part is
$$e^{-\sigma t}\cos \omega t$$
and the imaginary part is
$$e^{-\sigma t}\sin \omega t$$
Clearly, these are decaying (damped) oscillations which, as you might imagine, are very important in describing many physical systems.
So, while it's possible to avoid using complex frequency, it's much less convenient.


So when I read something about how fields fall into black holes and
  the modes consequently decay, why are the corresponding frequencies
  complex?

If the complex frequency is real, $\sigma = 0$, there is no decay, no dissipation.
A: Fourier frequencies, and particularly complex ones, are best thought about in terms of oscillating exponentials rather than sines and cosines. That is, you express the function of interest $f(t)$ as some sort of superposition (sum, series, or integral transform) of complex exponentials $e^{-i\omega t}$:
$$
f(t)=\sum_\omega\!\!\!\!\!\!\!\!\int \,a_\omega \times e^{-i\omega t}.
$$
Now, if your system is not closed for some reason and your modes decay (which is roughly what happens in quasinormal modes, but it also happens in a number of other settings, such as metastable resonances in quantum mechanics), then you can easily incorporate this by making the complex exponential have a bit of decaying exponential.
Thus, if your frequency $\omega$ has a negative imaginary part, so $\omega=\omega_0-i\gamma$ then each complex exponential can be written as
$$e^{-i\omega t}=e^{-i\omega_0 t}e^{-\gamma t}$$
and there you have your decay.
In essence, having a complex frequency allows you to encompass, using a single parameter, the oscillatory character of the mode and its decay properties. You don't have to start talking about complex numbers and you could keep both parameters separate, but this is always the way with complex numbers. You have two real numbers, $\omega_0$ and $\gamma$, such that your solution behaves as
$$
e^{-i(\omega_0-i\gamma)t}.
$$
I would say it is hard-headed not to recognize a combination of the form $\omega_0-i\gamma$ as a single complex number, but it is indeed doable, and you then have in practice twice as many parameters to keep track of. But, by this stage, it is all semantics.
A: The use of complex frequencies in physics rather common, so I will explain it in a general context. Probably it will be sufficient, otherwise somebody else can put it in the context of general-relativity. 
If you consider a mode of frequency $\omega = \omega_R + i\omega_I$ then the oscillation has time-dependence like $\exp(-i\omega t) = \exp(-i\omega_R t) \times\exp(\omega_I t)$
the first factor describes the periodical motion and the second factor the damping or the growth of this periodical motion. So if $\omega_I>0$, the periodical motion will grow exponentially, i.e. this motion will be unstable, whereas if $\omega_I<0$, the periodical motion will be damped exponentially or differently said the motion will decay. It can be seen that this growth or decay of the motion is related to the imaginary part of $\omega$.
Often $\omega_I$ is written like $\omega_I=1/\tau$ where $\tau$ represents the growth or damping time. The negative sign in the exponent \exp(-i \omega t) is pure convention, if it's changed, the definition of growth and damping also change sign.
This phenomena already can be studied in a damped oscillation or excited oscillation, for instance a spring plunged in a viscous liquid, the motion will described a product of periodical motion $\sin(\omega t)$ and $\exp(\omega_I t)$, $\omega_I<0$ if it's still difficult to grasp, just plot a curve in a graphics program: once only a $\sin(\omega t)$ and then $\sin(\omega t)\exp(t/\tau)$ with $\tau <0$ and once with $\tau>0$.
A: This the continuation of my comment: Every (real) quantity in time domain can be written like 
$$ A(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty}\mathrm{d}\omega\, a(\omega)\exp(i\omega t)  $$
In oder to guarantee the reality property of $A(t)$, $a(\omega)$ which in general takes on complex values has to fulfill $a^{\star}(\omega) =a(\omega^{\star})$ where again the complex frequencies enter. So computation in complex plane is rather convenient as long as some rules are respected. 
