An explanation of Hawking Radiation Could someone please provide an explanation for the origin of Hawking Radiation? (Ideally someone who I have been speaking with on the h-bar)
Any advanced maths beyond basic calculus will most probably leave me at a loss, though I do not mind a challenge! Please assume little prior knowledge, as over the past few days I have discovered that much of my understanding surrounding the process as virtual particle pairs is completely wrong.  
 A: I'm late to the party, but I would like to add a new answer in here that tries to capture the important features of Hawking radiation without diving too deep. Since there are already great answers in this post, I'll try to do something quite different, albeit a bit more pictorical. Here's a sketch of the approach I'll try to follow:

*

*brief review of some key concepts in Relativity

*energy is an observer-dependent concept

*what you call a particle depends on what you can energy

*since different observers have different notions of energy, they have different notions of what is a particle

1. Time is Relative
One of the most important predictions of Relativity (both special and general) is the relativity of time. While Galilean physics treats time as a universal parameter that independs on the observer, Einstenian physics treats time roughly as a coordinate. It is just as relative as space: when I say "This is two meters to the right", the words "two meters to the right" depend on me, and similarly saying "two seconds in the future" depends as well.
Without math, this is pretty much as far as I can go. Any book in relativity will discuss these things if you want a deeper explanation. There are posts on the relativity of time in this site (such as How can time be relative?, or Wrist watch close to a black hole), so I won't stay long in this.
Key point: what we call time depends on the observer. Time is not something universal and to define what we mean by time we must give a precise definition.
2. Energy is defined with respect to time
Next I consider the question "What is energy?" In layman's terms, I like to characterize energy simply as "a number that won't change with time". This is pretty much the most interesting thing about energy: it is conserved. If we were to call something else time, then that which we were calling energy would not necessarily be conserved anymore and the whole point of energy kind of goes away. Our interest in the concept of energy comes from the fact that it being conserved allows for our computations to be simpler.
This is a bit handwavy, but it can be stated more precisely as "energy is the Noether current associated with time translation symmetry". The ScienceClic's video The Symmetries of the universe is a particularly good introduction to Noether's theorem and it provides some intuition on how momentum is conserved due to translation symmetry and angular momentum is conserved due to rotational symmetry. Energy, similarly, is conserved due to time translation symmetry. Change what you call time and you are automatically changing what you call energy.
Key point: the notion of energy depends on the notion of time. Change the notion of time and you change the notion of energy. Since time is an observer-dependent quantity, so is energy.
3. Particles are an energy-dependent concept
I'll use an archaic view of particles in here that, in my opinion, has its pedagogical purpose. One of the weird predictions of relativistic quantum mechanics, and in particular of the Dirac equation, is that there were solutions to the quantum mechanical laws of motion that had negative energy. By "negative energy" I mean negative kinetic energy, the sort you really shouldn't have.
In order to understand this, Dirac proposed what is now known as the "Dirac sea". One of the properties electrons have are that no two electrons can occupy the same quantum state, which means they can't have the same properties at the same time. In a given atom, no two atoms can have the same energy, total angular momentum, angular momentum in a given direction, and spin at the same time. At least one of those has to be different. This is known as the Pauli exclusion principle.
In order to understand how the negative energy thing was possible, Dirac postulated that all negative energy states were always occupied with electrons, so they were not accessible to other electrons. In other words, it would be impossible for an electron with positive energy to drop to negative energies. Unless, of course, there was a hole in this sea of negative energy electrons. However, in this case, this hole would behave pretty much as a regular electron, moving around as if it had the same mass and so on. However, since it is surrounded by negative energy and negative charge (because electrons have negative charge), it would seem as a positive energy, positive charge particle: the positron, which is a form of antimatter. It is the antiparticle of the electron.
Notice then that the electrons we observe are associated with positive energy solutions (they are just the "usual" solutions), while positrons are associated with negative energy solutions. However, different observers have different notions of what is energy, and hence they might disagree on what is a solution with positive or negative energy. What one observer calls positive energy, another might say that has mixed positive and negative energy. Since the very notion of a particle depends on what one calls energy, the very notion of a particle is dependent on the observer.
You can learn more about the Dirac sea, for example, at PBS Spacetime's video Anti-Matter and Quantum Relativity.
I should point out the Dirac sea view is somewhat outdated in favor of the quantum field view favored in other answers. I'm talking about the Dirac sea in here because I believe it might provide some more intuition. It is problematic because the relativity of the notion of particles does not depend on the Pauli exclusion principle and Hawking radiation works for bosons too, not only fermions, but I think it might give an interesting picture.
Key point: the notion of particle depends on the notion of energy. Since energy is an observer-dependent quantity, so are particles.
4. There are two notions of time involved in gravitational collapse
Let me give an oversimplified version of gravitational collapse of a star: you have a star that is stationary (it does not change with time), it suddenly collapses to a black hole and, after some time, the black hole becomes stationary as well.
In the stationary eras, we have a well-defined notion of energy. In general relativistic language, we have a timelike Killing field. This is the sort of structure that we need to define energy in curved spacetimes. It is an appropriate notion of time that allows for a definition of energy.
However, in between these eras, you have some quite violent process that is not time-translation symmetric. Due to this, the two notions of time do not coincide. They lead to notions of energy that have no obligation to be equivalent, and they are not. Since you have different notions of energy before and after the gravitational collapse, you have different notions of particles.
What happens then is that an observer that shares the "natural" notion of time available at every point in his trajectory through the spacetime experiences two different notions of energy (with a transition phase in which energy is not really well-defined). Due to this change, the observer starts seeing no particles and eventually has a different notion of what particles are, and now sees particles. The lesson is that the notion of particles is not fundamental in physics, it is observer-dependent.
Notice this also explains the intuition behind the Unruh effect: an accelerated observer in Minkowski spacetime sees a thermal distribution of particles where a static observer sees none. I don't know of any analogy with virtual particles to interpret this effect, but in terms of how observer-dependent is the notion of particles it is straightforward: there is no a priori reason for two observers to see the same particle content.
Let me finish by mentioning that in usual particle physics none of this is an issue: one can show that all inertial observers in Minkowski spacetime will see the same particle content, and hence the experiments that take place at the LHC, for example, will always have the same notion of particles.
A: 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.
A: @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.
