The Entropy of Black Holes
The idea that black holes should have an entropy value associated with them was first championed by Jacob Bekenstein. It had been noticed by Stephen Hawking and others that the law 'the event horizon area of a black hole must always increase' is very similar to the second law of thermodynamics; 'the entropy of a closed system must always increase'. This was somewhat heretical, as this implies a black hole should have a randomness associated with it. It was known at the time a hole could only have the properties of mass, spin, and charge; which is about as non-random as you can get.
Bekenstein was convinced though, as without giving the hole entropy, meant it could violate the second law of thermodynamics, something that he felt very strongly that it should not do. An example of how black holes could break the law (that the entropy of the universe should always increase) is as follows: My room is a real mess, full of junk I haven't tidied up, stuff I've stepped on and broken, coffee I've let go cold, and then I go and set it on fire...I can hide my crime of letting the entropy increase from the Lords of The Universe, by simply dropping my room down a handy black hole. That should, according to the traditional viewpoint, render the entropy of my room back to zero! Bekenstein thought that was wrong, somehow the area of the event horizon must be related to the entropy; most others including Stephen Hawking thought that entropy loss was just a natural feature of black holes. John Wheeler however told Bekenstein 'Your idea is just crazy enough it might be right' Bekenstein continued his work on this; and by looking at how a mass; with entropy associated with it, would have to increase the holes area and entropy, came up with a relationship between the two.
Black hole entropy = Horizon Area / Planck-Wheeler area
So if you drop a mass down a black hole, its entropy may be increased to a maximum, the value of which is determined by the above relationship.
For a 10 solar mass black hole this works out to be about 1079, meaning whatever the hole contains, it can be arranged in about (1010)79 ways! Which again is nonsense, as classically all that black holes can contain is the singularity, and nothing else.
At a conference in 1972 in the French Alps James Bardeen, Brandon Carter and Steven Hawking were working on the laws of black hole mechanics. What they came up with looked exactly the same as the laws of thermodynamics, if you replace entropy with 'horizon area' and surface gravity with 'temperature'. Everybody thought that this proved the case that black holes can not have entropy, if they did the horizon must have a finite temperature, which is impossible because black holes can't radiate! Even Beckenstein agreed to an extent, he knew black holes couldn't have a temperature, but still he thought that somehow they must have an entropy.
In 1974 Stephen Hawking proved (in one of his most dramatic theories) by marrying quantum mechanics to general relativity that a black hole would evaporate, and would have a temperature proportional to it's surface gravity. He had changed his mind, and asserted that the black hole mechanics laws and the thermodynamic laws are the same thing, and he refined Beckenstein's relationship ship into :-
BH entropy = ((1/(4loge10)*surface area)/Planck-Wheeler Area
Black Holes and Information Loss
This is all very nice, and it all hangs together, but the information theorists among you may well be asking 'So what about the information loss?' Well, yes that is a problem and to see why, the following example can be used :-
My own Ramblings
Take a quantum system in a pure state, of mass Q, and throw it down a black hole of mass M, you now have a hole of mass M+Q with a corresponding larger entropy. Now wait until the hole has Hawking irradiated away enough mass to return to mass M. So what you've done is transformed a pure quantum state into a thermal one via the Hawking radiation, which constitutes a loss of information. It can't be down the black hole (according to current theory) as all the information the hole can hold is spin, charge, mass and entropy, all of which have returned to their original values! Again this problem hints at some deep process going on, where relativity and quantum mechanics fail to meet. Superstring theory may well be able to patch up the join, recent results on a type of (mathematically constructed, not real) black holes, so called extremal black holes have shown it is possible to count the number of string states that could contribute to a black hole of a given mass. This entropy is exactly the same as that given by the above formula.
Now I'm not a physicist, so I'm afraid I'm not too sure how relevant my following ideas are, but well anyway this site can stand a bit of personal input.
If all a black hole can contain is the singularity, perhaps another way of looking at the entropy is to say that is contained not around the horizon of the hole, or within the volume of the horizon, but in the singularity itself. The current 'best picture' of the singularity; based on new work such as quantum gravity, superstring and m-theory is that it is a quantum foam. Perhaps the geometry and topology of this foam is related to the entropy of the hole itself. Maybe you could think of the Hawking radiation particles emitted from the horizon, as quantum tunneling out of the singularity itself, the exact nature of the particles emitted, limited by the topology of the quantum foam. When the hole is large, its entropy will be corresponding large as will the wavelength of particles emitted by the Hawking radiation. I visualise the singularity of a large black hole as (relatively) stable, meaning it is constrained only emit strings of large wavelength. As the hole shrinks, its entropy decreases, the turbulence of the singularity increases, and the wavelength and energy of the particles emitted increases.
This may answer the information loss problem also; perhaps throwing quantum states down the black hole changes the quantum state of the singularity. This provides an extra parameter to a black holes description, now we have mass, spin, charge, entropy, and the quantum state of the singularity. Now in the above example when the hole goes from mass M+Q back to mass M, it may not be the exact same hole it was, the quantum state of the singularity will have changed. An interesting experiment to perform might be to feed a black hole many identical quantum states, and see if the nature of the Hawking radiation can be affected.