I just spent about three minutes talking to the BBC World 6 o'clock news anchor (Nik Gowing) about Black Holes, quantum mechanics, and information. (And allowed the BBC's budget to shuttle me from Imperial College to White City and finally to Paddington.) He was perhaps less interested in the science than in Hawking's bet with John Preskill (which Hawking will actually lose if his new idea turns out to be correct).
The question, and the paradox, is this. The first ingredient is that, in Einstein's General Relativity, "Black Holes have no hair". That is, no matter what you throw into them (TV sets, The New York Times, mud) all that's left at the end of the day is the total mass, total charge, and total angular momentum (that is, how fast it's spinning) of what was thrown in.
The second ingredient is Quantum Mechanics, in particular a property of quantum mechanics called "unitarity" which, in this context, means that you can't take a highly-ordered system (the TV sets, newspapers, or mud) and make it into an unordered system without acting on it from outside. This is fine in a classical black hole: all that information, all that order, is locked away inside the black hole, inaccessible to the rest of the Universe.
The paradox comes from Hawking's own work: Black Holes are not actually black, but if sitting there in the vacuum of space, actually radiate away at a particular temperature (known as the 'Hawking Temperature') related to the mass of the Black Hole. In this original theory, the radiation is completely featureless, a so-called "black body" -- radiation with much less order than whatever was originally thrown into the black hole. So here's the paradox, then. Throw stuff into a black hole, wait long enough, and you find that the universe is a much less ordered place than it started.
Physicists have been thinking about this problem ever since Hawking's original calculation, and many solutions have been proposed; we won't know until next week (or perhaps after that when all the peer-review dust has settled) if this proposal is the right answer and (perhaps more importantly) whether it gives any insight into the more fundamental problems underlying the paradox: the relationship of General Relativity and Quantum Mechanics, the role of information in fundamental physics, and the meaning or probability.
Of course I didn't get to say all this to the BBC. I know the chances of anyone reading this having seen my "performance" is pretty slim, but if you have, please leave me a comment!! (And let me know if my version was any better than Hawking himself on "Newsnight"!)