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.
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.