The information paradox arises if we assume that the effects of quantum gravity extend only over Planck distances. String theory, as a complete theory of quantum gravity, must offer us a way out of this paradox. The way it does this is that string theory states "puff up" in proportion to the number of quanta they carry, changing the notion that there is no information stored near the horizon.
There have been some comments on this blog regarding the classical / quantum nature of microstates. Here are my brief comments on the issue; for more details one can look at the reviews hep-th/0502050 or hep-th/0510180. More details on the nature of states etc can be found for example in hep-th/0607222, hep-th/0609154.
The simplest model is the 2-charge extremal hole. We can dualize the charges to NS1-P; that is, a string carrying momentum. The total winding and momentum are taken large, so that we can match the entropy to the Bekenstein-Wald classical value.
The entropy arises from the way the momentum can be partitioned among harmonics. Let us first look at some special (i.e. non-generic) states. The simplest possibility is to put all the momentum into a large number of units N of the lowest harmonic. Recall that each Fourier mode of vibration is a harmonic oscillator. Thus the lowest frequency oscillator is in the state /N>. Since N is large we expect some classicality. To get classical motion we can replace /N> by a suitable superposition of states ... /N-10>, /N-9>, ... /N+10> ... This makes a coherent state, which gives a classical "pendulum motion" to the oscillator. The string then carries a helical wave, with a small quantum spread (order 1/N) around the helical profile. The generated metric will also be close to classical, with a small ~1/N order spread from quantum fluctuations.
We already see a key feature: the transverse oscillations of the string give it a transverse size that grows with N. Dualizing to D1-D5, the geometry has a "throat", but instead of ending at a point-like singularity, it ends in a locally AdS3 "cap".
Now let us split our energy among, say, five different harmonics. This gives more complicated string profiles, but also note that since the occupation number N of each mode is smaller, the quantum fluctuations are slightly larger. But since N was big to start with, we can still think of a family of classical string profiles.
The generic state of the string is given by a thermal distribution of vibrations. The occupation number for harmonic k is
- n(k) ~ 1 / [ exp(k / sqrt N)-1]
How big is this fuzzball? We are given a total energy of excitation. One finds that the transverse size of the state depends on the mean harmonic number that is excited, while the fluctuations depend on the occupation number of the typical mode. So to estimate the size of the generic state we take the wavenumber k=sqrt(N) and put all our energy in it - this gives an occupation number sqrt(N) >> 1 so we can use the classical profile description. One then finds a size that is just the order of the horizon radius of the 2-charge hole, so fuzzballs are horizon-sized objects. Now imagine splitting the energy into more modes, still with sqrt(N) as the mean. The size remains the same, while the fluctuations grow larger. Finally, we reach the generic state where the size is as computed, but fluctuations are O(1).
I would expect that this general idea remains true for 3 and 4 charge systems ... special states can be classical and help us to understand the behavior of generic states; the generic states themselves are very quantum "fuzzballs". Iosif Bena has talked of a "strong form" of the general conjecture where the situation is as above for 2-charge, but the states become much more classical for 3-charge. I do not understand these arguments well, so I will take my conservative view that for all cases the generic states are very quantum string-theoretic objects.
The work of Bena-Warner has shown that large families of 3-charge objects can be made by having different arrangements of "dipole charges". These can be reduced to 4-D by a method of Bena-Kraus, and Balasubramanian-Gimon-Levi have obtained large families of four-dimensional solutions with different locations of poles containing different possible dipole charges. The simplest cases have just two poles, but as we go to a limit where the numbers of these poles becomes large I would expect that quantum effects set in - stringy degrees of freedom get excited between the charges at the poles, and all we can say is that we have a very "quantum fuzzball". For the non-BPS hole one would use brane-antibranes degrees of freedom, which will generically give a very quantum state, too.
(Gautam Mandal commented that a similar thing happens in LLM: when all the fermions are in their lowest state we can write a classical geometry, but for a general state of the fermions we will get large fluctuations.)
Thus the important point of the fuzzball proposal is that the size of the bound state is always large (horizon size) and not Planck size. Classical solutions are obtained for specially chosen microstates, but these help us understand the size of the generic state. The throats of extremal holes end in "fuzzy caps" rather than in a horizon, and this solves the information puzzle.