An explanation of Hawking Radiation
To answer this we need to talk a bit about how particles are described in quantum field theory.
For every type of particle there is an associated quantum field. So for the electron there is an electron field, for the photon there is a photon field, and so on. These quantum fields occupy all of spacetime i.e. they exist everywhere in space and everywhere in time. It’s important to realise that a quantum field is a mathematical object not a physical one - more precisely it is an operator field - however it’s common to talk as if quantum fields are real objects and I’m going to commit this sin in my answer. Just be cautious about taking it too literally.
Anyhow, quantum field theory describes particles as excitations of a quantum field. If we add a quantum of energy to the electron field it appears as an electron, or if we take out a quantum of energy from a quantum field that makes an electron disappear. Incidentally this explains how matter can turn into energy and vice versa. For example in the Large Hadron Collider the kinetic energy of the colliding protons can go into excitations of quantum fields where that energy appears as new particles.
The vacuum state of a quantum field is the state that has no particles. For a quantum field there is a function called the particle number operator that returns the number of particles present, and the vacuum state is the state for which the number operator returns zero. So when we talk about the vacuum in physics we are really referring to a specific state of quantum fields.
Quantum field theory is designed to be compatible with special relativity, and the vacuum state is Lorentz invariant. That means all observers in constant motion in flat spacetime will agree what the vacuum state of the field is. The problem is that the vacuum state is not invariant in general relativity i.e. in curved spacetime. In a curved spacetime different observers will disagree about how many particles are present and therefore will disagree about the vacuum state.
Specifically, and this is step one in our attempt to explain Hawking radiation, observers near and far from a massive body will disagree about the vacuum state. Suppose you are hovering near a massive body like a black hole while I’m hovering a long way away from the body. The quantum field state that looks like a vacuum to you will look to me as if it contains a non-zero number of particles.
I’m not sure it’s possible to explain simply why the vacuum state looks different to different observers in a curved spacetime because it’s related to the procedure used to quantise a field (expanding it as a sum of oscillatory modes) and that’s too complicated a process to do justice to here. Maybe that could be the subject of a future question, but for now we’ll just have to take it on trust.
Anyhow, you’ll note that a couple of paragraphs back I mentioned that the disagreement about the vacuum was just the first step to explaining Hawking radiation. That is because the fact two observers disagree about the vacuum state does not necessarily mean energy will flow from one observer to the other i.e. a flow of radiation. Indeed, unless an event horizon is present there will be no flow of energy - for example a neutron star does not emit Hawking radiation, and neither does any other massive object unless a horizon is present. The next step is to explain the role of the horizon in the Hawking process.
For a black hole to evaporate, energy has to completely escape from its potential well. To make a rather crude analogy, if we fire a rocket from the surface of the Earth then below the escape velocity the rocket will eventually fall back. The rocket has to have a velocity greater than the escape velocity to completely escape the Earth.
When we are considering a black hole, rather than the escape velocity we consider the gravitational red shift. The red shift reduces the energy of any outgoing radiation, so it reduces the energy of any radiation emitted by the hotter vacuum state near the event horizon. If the red shift is infinite then the emitted radiation gets red shifted away to nothing and in this case there will be no Hawking radiation. If the red shift remains finite then the emitted radiation still has a non-zero energy as it approaches spatial infinity. In this case some energy does escape from the black hole, and this is what we call the Hawking radiation. This energy comes ultimately from the mass energy of the black hole, so the mass/energy of the black hole is decreased by the amount or radiation that has escaped.
The problem is that at this point I find myself completely lost for a way to describe this that is comprehensible to the layman. In Hawking’s original paper from 1975 he calculates the scattering of the particles emitted in the Hawking process, and he shows that in the presence of a horizon the scattering is modified because everything inside the horizon cannot contribute. The result of this is that the red shift remains finite and as a result we observe Hawking radiation i.e. a steady stream of radiation completely escaping from the black hole. Without the horizon the red shift becomes infinite so no energy escapes and no Hawking radiation is seen. That’s why objects without a horizon, e.g. neutron stars, do not produce Hawking radiation no matter how strong their gravitational field is.
Hawking himself uses the analogy of virtual particles in his paper. He says:
One might picture this negative energy flux in the following way. Just outside the event horizon there will be virtual pairs of particles, one with negative energy and one with positive energy.
However he goes on to say:
It should be emphasized that these pictures of the mechanism responsible for the thermal emission and area decrease are heuristic only and should not be taken too literally.
What he is actually calculating is how a wavepacket (which a free scalar quantum field is) behaves when scattered off a black hole in the process of forming, and then comparing the old and new frequencies of oscillation, which are how we get a notion of particles and vacuum, as noted in passing above. Given that Hawking said this in his original paper in 1975 it is something of a shame that the pairs of virtual particles analogy is still being trotted out as an explanation for the process some thirty years later.
Footnote
I’m not altogether happy that I have done justice to the Hawking process and radiation. In particular I don’t think I’ve really explained why a horizon is necessary - maybe it is simply impossible to explain this at the layman level. However since I have run out of steam I’ve decided to post this in the hope it will be helpful.
I’ve made this answer community wiki because it is the result of contributions from many people, mainly in the hbar chat room. If anyone thinks they can improve on this I encourage them to post their updated version as an additional answer, and we can edit it into this answer to hopefully come up with something both authoritative and comprehensible.
Finally we should note that although Hawking's original paper was met with some debate, for example due to the use of trans-Planckian modes, the phenomenon is now well understood and the mathematical treatment is universally accepted. We even have an exact solution for the simplified case of a free scalar field (though this doesn't include the effects of back reaction). If experiment (asuming we are ever able to do the experiment) fails to find Hawking radiation that will require a root and branch re-examination of our understanding of QFT in curved spacetimes.
@JohnDuffield: I can give you both a correct answer in simple terms and the fairy tale, together with references to an explanation how the fairy tale is related to the real thing!
The dry facts are that two real particles (e.g., two photons, or an electron and a positron) are created from the energy in the very strong gravitational field near the horizon of the black hole - from a classical external gravitational field (if gravitation is treated classically), or possibly from two gravitons (in effective quantum gravity at lone loop), not from the vacuum. [Strong external fields with energies significantly above the pair creation energy threshold necessarily create the corresponding particle pairs. See the postscript below for more details.] The particle pair creation reduces the gravitational energy by the energy (including the rest mass energy equivalent) of the two particles. One particle escapes, the other is absorbed by the black hole. The net result (black hole energy - 2 particle energies + 1 particle energy) is a loss of mass corresponding to the energy of the escaping particle. A valid description is given on p.645 of the book B.W. Carroll and D.A. Ostlie, An Introduction to Modern Astrophysics, 2nd. ed., Addison Wesley 2007.
A corresponding animated (hence much more impressive) virtual ghost story for the general public - with all the common misconceptions characterizing these - can be found on Steve Carlip's site. Note that he warns his readers (earlier on the cited page): ''Be warned - the explanations here are, for the most part, drastic oversimplifications, and shouldn't be taken too literally.'' Those who copy from him (or from similar sources with similar caveats) usually take the fiction painted for scientific fact. But just because the fiction stems from a well-known scientist, it doesn't become science!
Facts and fiction about virtual particles are thoroughly distinguished in my article Misconceptions about Virtual Particles. The above is essentially taken from the discussion page of this article, where more discussion of the Hawking effect can be found. Also discussed there (in post #58) is how the fairy tale is related to the real thing.
John Baez wrote another useful scientific account of Hawking radiation.
A 2010 paper by Padmanath describes the facts in much more detail taking 7 pages, and ends the description on p.8 with an informal paragraph containing a short version of the common fairy tale, introduced with the the sentence ''One picturesque way to understand what is going on is to think of vacuum fluctuations being represented by virtual particle-antiparticle pairs popping in and out of existence.''. As everyone using such fairy tales, he says nothing at all about how the fairy tale could be grounded in real physics, and hence why it should contribute to understanding. - It only illustrates the physics, in the same way as a cartoon illustrates politics or other topics.
Postscript. In canonical gravity (an effective theory, the best working approximation to quantum gravity we currently have), gravitons exist though they haven't been observed.
The local energy density is well-defined as the 00 component of the stress-energy tensor. It is frame dependent but in locally strong fields it is locally large in every frame. In the quantum version, a strong gravitational field is like a strong electromagnetic field, described not by an empty vacuum state but by a state full of energy (as defined by the energy-stress tensor).
The space-time inhomogeneity due to gravitation is described by a massless tensor field called the gravitational field (or the metric, in a geometric view that doesn't survive quantization). In canonical quantum field theory, which must be used in order to describe particle production, space-time is just a smooth manifold without predefined metric. The gravitational field (i.e., the quantized metric) is now described by a massless quantum field tensor operator that gives rise in the usual way to creation and annihilation operators for gravitons.
Just as particle pair production from strong electromagnetic fields is inevitable through processes such as $2\gamma\to e^-+e^+$, where $\gamma$ denotes a photon, so particle production from strong gravitational fields is inevitable: If one looks at the S-matrix in the tree approximation of canonical quantum gravity + QED, one gets processes such as $2g\to 2\gamma$ and $2g\to e^-+e^+$, where $g$ denotes a graviton. The first process happens at any positive energy since both sides are massless; the second process happens once the local energy concentration exceeds the energy equivalent of two electron masses.
Since only the tree approximation is invoked, one does not need to worry about unsolved problems about renormalization in quantum gravity, which would provide only minor corrections.
[added January 11, 2017] I recently discovered that already in his ground-breaking paper on the subject, Hawking says on p.2462 (left) that ''One can interpret such a happening as being the spontaneous creation in the gravitational field of the black hole of a pair of particles, one with negative and one with positive energy with respect to infinity. The particle with negative energy would fall into the black hole [...] The particles with positive energy can escape [...]''. (Note that only energy differences are meaningful, hence Hawking's reference to (zero energy in flat space at) infinity that gives meaning to the sign of the energy.) No "virtual pairs" of particles and antiparticles that pop in and out of existence, as in Carlip's fairy tale! For those interested, I collected together in my article The Vacuum Fluctuation Myth many of the subtle observations that come together in the fabrication of the myth.
Note that it doesn't matter whether the gravitational field is treated by classical or quantum mechanics; this only gives extremely tiny corrections to the exact rates. Calculations are usually done semi-classically, i.e., treating gravitation as classical external field. But getting essentially the same results from quantum gravity is considered as one of the tests that a quantum theory of gravity must pass to be regarded as a serious candidate.