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.