Original by Warren G. Anderson 1996.
In 1975 Hawking and Bekenstein made a remarkable connection between thermodynamics, quantum mechanics and black holes which predicted that black holes will slowly radiate away. (see Relativity FAQ Hawking Radiation). It was soon realized that this prediction created an information loss problem which has since become an important issue in quantum gravity.
In order to understand why the information loss problem is a problem, we need first to understand what it is. Take a quantum system in a pure state and throw it into a black hole. Wait for some amount of time until the hole has evaporated enough to return to its mass previous to throwing anything in. What we start with is a pure state and a black hole of mass M. What we end up with is a thermal state and a black hole of mass M. We have found a process (apparently) which converts a pure state into a thermal state. But, and here's the kicker, a thermal state is a MIXED state (described quantum mechanically by a density matrix rather than a wave function). In transforming between a mixed state and a pure state, one must throw away information. For instance, in our example we took a state described by a set of eigenvalues and coefficients, a large set of numbers, and transformed it into a state described by temperature, one number. All the other structure of the state was lost in the transformation.
In technical jargon, the black hole has performed a non-unitary transformation on the state of system. As you may recall, non-unitary evolution is not allowed to occur naturally in a quantum theory because it fails to preserve probability, ie, after non-unitary evolution, the sum of the probabilities of all possible outcomes of an experiment may be greater of less than 1.
In the face of such evolution, quantum mechanics falls apart, and we are faced with a dilemma. Do black holes really defy the tenets of quantum theory, or have we missed something in our thought experiment. Perhaps the black hole is not the same after it has evaporated to mass M as it was initially at mass M. Or perhaps there is some subtle correlation in the Hawking radiation that we are missing, but that supplies the missing information about the pure state.
This, then, is the black hole information loss problem. The fact that information is lost is reflected in the thermal nature of the emitted radiation. But any thermal system can be assigned an entropy via the Gibbs law dE = S dT. Thus, we can calculate the black hole entropy by dint of the fact that we can calculate the black hole temperature (by dint of the fact that the quantum radiation is thermal). This is, I think, what people are getting at when they say that black hole entropy is responsible for the information loss. I would say it the other way, that black hole information loss is responsible for black hole entropy. The simple fact of the matter is that they are the same thing in slightly different terms.
Two notes to finish off. First, you might think that the thermal nature of the black hole is inevitable since it is radiating, but you would be wrong. In most of these quantum radiation calculations, the spectrum of the radiation does not have a Planck spectrum. If that had been the case for black holes, too, then we would not be able to assign a temperature or an entropy to black holes. In that case, people probably still would not believe Bekenstein and instead of the information loss paradox we'd still be wondering how to reconcile black holes with the second law. The thermal spectrum of Hawking radiation is one of the most serendipitous results in modern physics, in my opinion, which is another way of saying that something deep and not understood is going on.
The second is an interesting sidelight. While it's true that the Gibbs law gives the correct Bekenstein-Hawking entropy from the calculated temperature, no one has been able (until a few months ago) to explain the entropy directly from quantum mechanical / statistical mechanical grounds. In fact, it has been proven that semiclassical gravity is insufficient to account for this entropy. This is a profound result, since the thermodynamical entropy is obtained at a semiclassical level (in fact, due to some quirks which I suspect are related to the non-linearity of gravity, it is essentially classical). Thus, we are faced with the disconcerting choice that A) thermodynamical entropy does not always have a statistical mechanical basis or B) gravity is not a fundamental interaction, but rather a composite effect of some more fundamental underlying theory. Option B is not disconcerting to superstring theorists, however, it is exactly their point of view. Interestingly, since about the beginning of the year, the superstring people have jumped into the "origin of black hole entropy" fray. It turns out that by using some old result about monopoles in certain types of field theories they have been able to count the string states that would contribute to a certain (unphysical) class of a black hole of a given mass. The entropy is exactly that given by the Bekenstein area formula. The experts assure me that this will be extended to more physical models in the future. An exciting prospect indeed, if it pans out.