If nothing ever falls into a black hole, why is there a puzzle about information? From an outside perspective, nothing can ever pass the event horizon. It just scooches asymptotically close to the event horizon.
So (from our perspective on earth), when a black hole reduces in mass, is recovering the information just as simple as scooching the same material back away from the event horizon?
 A: One problem is that nothing special happens at an event horizon.
For instance, point your finger straight up.  For all you know very very very far away in that direction there is a very very very massive black hole.  It could be so massive that it's Schwarzschild radius is 100 billion light years.  And you could be sitting right on the horizon because it is that far away.  So at any moment you might be crossing an event horizon, and if it is a big horizon, the tidal effects would be too weak for you to notice.  So there just isn't any practical way to just be sure you are outside all blackholes.  So the distinction between outside and inside isn't always a practically actionable one, we need theories that can handle both outsides and insides, at least for weak tidal effects.
OK.  Next, there is another way to be inside a black hole beside crossing an event horizon.  Imagine your friends arrange a giant spherical shell of matter around you.  Locally you don't notice a single thing (not even tidal effects, nothing at all).  Globally you notice that things outside the shell move and age faster than they used to.
Now your friends contract the sphere.  That effect gets larger.  You friends can compress the sphere more and more.  They might even give each piece some kinetic energy enough that it will keep compressing for a while without them staying there to keep pressing it.  And if they pushed it hard enough, a black hole event horizon will form.  And you'll be on the inside.
But wait.  What do I mean by it will form?  There is a region outside the sphere where your are too far away and have too little time, your friends cannot get the event horizon to stop it from forming.  From their point of view, while they haven't seen it happen, they know there is nothing they could do to stop it, it's a "fate accomplished", but whether something else stopped it is actually still a question, so it's not really accomplished because they don't know if actually forms, just that there isn't anything they can do to stop it on their own.
A: Consider a spherical symmetric mass distribution in space, located around the origin of a coordinate system. One can forumlate a stress-energy-tensor $T^{\mu,\nu}$ for this situation. Solving the Einstein-field-equations for a reference frame, in which that mass distribution is not moving one obtains the Schwarzschild-metric $g_{\mu,\nu}$.
One can now try to find the path $x^\mu$, on which a particle moves, if it is exposed to the attractive gravitational "force" (see below for clarification) of that mass distribution.
One usually does that like this:
If the particle is left alone, it will travel on the path with least length from point A to point B, that is it will minimize the path length
$$ L = \int ds = \int \sqrt{g_{\mu,\nu}(\lambda) \frac{dx^\mu}{d\lambda} \frac{dx^\nu}{d\lambda}}\ d\lambda $$,
similar to the least action principle in classical lagrangian mechanics (see this for a exemplary calculation in special relativity / flat spacetime).
Here $\lambda$ is an arbitrary parametrisation of the path $x^\mu(\lambda)$.
From this, one obtains differantial equations (the equations of motion) for $x^\mu$. If we take $d\lambda = d\tau$ with $\tau$ proper time, we get the geodesic equations:
$$ \frac{d^2x^\mu}{d\tau^2} = - \Gamma^\mu_{\ \ \alpha,\beta} \frac{dx^\alpha}{d\tau} \frac{dx^\beta}{d\tau} $$.
The right hand side can be thought of, as the gravitational "force" (see above). Solving those equations, one finally obtains the path of the particle. This solution is subject to two inital conditions, e.g. inital velocity $\frac{dx^\mu}{d\tau}(0)$ and position $x^\mu(0)$, as this is a second order ordinary differential equation.
There is a border called "event horizon" or Schwarzschild-radius $R_S$, for that, if the particle is initially inside this horizon, there exists no initial velocity $|\frac{d\vec{x}}{dt}| = v \le c $, such that the particle can ever get outside. Equivalently: There is no path from within the event horizon to its outside. If the mass distribution is supported in the horizon, the situation is usually called a black hole. In a similar way one finds: There is no path from the outside to the inside.
Consider the following example: Take spherical coordinates and assume the particle is initially at rest in radial direction, that is $\frac{dr}{dt} = 0$, at some radius $r=R > R_S$. Solving the geodesic equations, one finds for the elapsed time $\Delta t$ for the particle to travel to the radius $R_S \le r < R$:
$$ \Delta t = \sqrt{\frac{R}{R_s} - 1} \left( (\frac{R}{2} - R_S)\cdot \alpha + \frac{R}{2}\cdot \sin(\alpha) \right) + 2 R_S \cdot \tanh^{-1} \left( \sqrt{\frac{\frac{R}{r}-1}{\frac{R}{R_S}-1}} \right) $$
with $\cos(\alpha) = \frac{2r}{R} - 1$ (see this for calculation and ignore everything beyond the above result). The first term is alright but the second is problematic since $\tanh^{-1}(\dots) \rightarrow \infty$ as $r \rightarrow R_S$. So we have $\Delta t \rightarrow \infty$ as $r \rightarrow R_S$.
For a light signal directed along the radial component we have:
$$ dt = \pm \frac{1}{1-R_S/r}~dr $$
and therefore for the time that the light signal takes to go from $R$ to $r$:
$$ \Delta t' = \Delta r - R_S\ln\left( \frac{r-R_S}{R-R_S} \right) $$
with $ \Delta r = R - r$. Similar we have $\Delta t' \rightarrow \infty$ as $r \rightarrow R_S$
In short: It takes an infinite amount of time to approach the event horizon of a black hole. Nothing will ever fall into it! Note that this holds for an observer that is at rest relative to the mass distribution. For this observer there is no information paradox or anything else.
Now what happens for an observer that travels with this particle? The particle is falling freely so its own reference frame is an inertial system (equivalence principle)! That is, there is no curvature of space if things are observed relative to the particle (this can be shown entirely by coordinate transformation). For this observer, apparently, there is no black hole, Schwarzschild-radius, event horizon or anything like that. Nevertheless, he will still approach the mass distribution. For him, when he has traveled to the radius $r$ relative to the first observer, the proper time
$$ \Delta \tau = \frac{R}{2} \sqrt{\frac{R}{R_S}} \left( \alpha + \sin(\alpha) \right) $$
will elapse. This is finite for all $r$. He can get pass the point, which the other observer would call an event horizon.
$$$$
Still, there should be said someting about idealisation here:
We assumed that the mass distribution is at rest relative to some observer. I'm not sure at which rate of acceleration spacetime becomes flat enough to let go of the properties like event horizon etc. (apperently the free fall acceleration does the job but there could be an intermediate border). Also, we assumed the particle to be entirely massless (since we have not considered its mass $m$ in the mass distribution). This is a good approximation if $\frac{m}{M} << 1$, where $M$ is the total mass of the initial mass distribution. Still there might be some non-continious change in the behaviour for $m \ne 0$. I have never done such exact calculations in the above manner. So take all this with caution.
A: You can't "scootch the material from the event horizon" because in the coordinates of anything approaching the hole, the matter does in fact fall in. However, you could study for example radiation from the matter.
This is thought not to resolve the paradox for several reasons (note I gave a very similar answer to Can the event horizon save conservation laws for black holes?. I think this is an appropriate answer to both.):


*

*Real matter is quantized. The exponential redshift thus eventually leads to a sitatuation where there is a "last quantum" to fall into the hole. Eventually, it does fall in, and the matter is truly gone.

*The hole will eventually decay into Hawking radiation. Once this process is complete the infalling matter will be truly gone, replaced entirely by Hawking emission, even according to the distant observers. But the Hawking radiation doesn't seem to be entirely determined by the matter, so information seems to be lost. We know the information is not in fact lost because the black hole is mathematically equivalent to a certain conformal field theory, which preserves information by construction. Hence the paradox.
One might then offer the following also-standard response to objection 2:
This objection shows only that something strange must be happening during the actual destruction of the hole. But this is obviously a quantum gravity effect. Thus there is no need to modify our understanding of what happens to the information before the decay: it just stays painted on the horizon until the hole is destroyed.
Some canonical responses are:


*Remants seem absurd. If this response were taken seriously, it would essentially imply that all the information about the black hole - an object of potentially arbitrary mass! - can somehow be contained within a Planck-scale volume. This would be very odd.

*Page timescale. It can be shown that about the first half of the black-hole information must be emitted over the same "Page" timescale as it takes to emit about half of the mass. This seems to imply that something poorly-understood is going on even while the hole is large.
A: From an outside perspective, things falling into the event horizon would have their light emission redshifted to the point where we'd just see them fade away. From the perspective of the object falling into the black hole, the object does indeed cross the even horizon. At this point the information about the object is considered destroyed, since it can in no way be accessed or observed anymore, because the extreme curvature of space time near the black hole prevents the object from "sending" any information to outside observers once it is inside the event horizon. 
Even if you assume the black hole would lose its mass by emitting say, Hawking Radiation, there would still be  loss of information. It wouldn't be the same as "scooching the material away from the event horizon". If the object entering the black hole had a pure quantum state (i.e the information.), the transformation of it into Hawking Radiation would destroy the information about the original state, (the radiation leaving the black hole would be completely independent of the type of object that fell in) hence leading to the puzzle about information. 
