In classical physics, there is no black hole information loss paradox: the information is lost, and that's all there is to it. No paradox. (See Ben Crowell's answer.)
The famous "black hole information loss paradox" comes from considering the behavior of quantum fields in the background spacetime of a black hole formed by a collapsing star. That analysis gives us a compelling reason to believe that a black hole eventually evaporates due to Hawking radiation. After it evaporates, presumably nothing is left — no event horizon, no singularity.
The problem is to explain how the information about everything that fell into the black hole gets back out by the time the black hole is done evaporating. The seemingly-obvious answer is that it comes back out gradually via the Hawking radiation, just like information that was written on a piece of paper and then burned would be encoded (in a practically useless scrambled form) in the light, smoke, and atmospheric molecular motions that are produced by the burning process.
Presumably the information eventually does come back out (in scrambled form) via the radiation, but the challenge is to explain how that happens. The naive analogy with a burning piece of paper doesn't work, at least not as far as we can tell using the standard approximation that was used to derive Hawking radiation in the first place. Luboš Motl's answer to the question
Why isn't black hole information loss this easy (am I missing something basic)?
addresses this very briefly, and several reviews on arxiv.org address it in more depth. One example is [1], which says:
conventional physics implies the Hawking effect to differ fundamentally from familiar thermal emission from hot objects like stars or burning wood.
The difference (explained more carefully in [1]) is related to the fact that when we burn a piece of wood or paper, the original information ends up being stored in subtle correlations across the resulting light, smoke, atmospheric molecular motions, and so on; but for a black hole, because of the way Hawking radiation works, Hawking-radiation modes that were emitted at different times cannot be correlated with each other in that way, at least not within the approximation that is normally used to derive the radiation in the first place. (The Appendix offers a few comments about that approximation.)
The black hole information paradox is especially paradoxical because the aforementioned approximation is expected to be adequate during most of the black hole's lifetime, but in the final moments when the approximation is expected to fail, there isn't enough of the black hole left to restore the necessary correlations. In one author's words [2]:
The black hole information paradox forces us into a strange situation: we must find a way to break the semiclassical approximation in a domain where no quantum gravity effects would normally be expected.
Like any paradox, this one will presumably be resolved after we learn how to formulate the problem properly. As noted in the Appendix, this requires using a theory of quantum gravity (but see the Edit at the end), and it is still an active area of current research.
Appendix: The approximation used to derive Hawking radiation
Hawking derived Hawking radiation using an approximation that considers the behavior of quantum fields in a prescribed spacetime background. (Most modern reviews derive it essentially the same way.) The prescribed background corresponds to the black hole formed by a collapsing star. This approximation violates the "conservation of energy," because the spacetime background affects the behavior of the quantum fields (leading to Hawking radiation), but the quantum fields don't affect the spacetime background. In particular, the black hole doesn't actually evaporate in this approximation, even though it does radiate. This is acknowledged in [3]:
Hawking's original derivation... considered a quantum scalar field propagating on a fixed [aka prescribed], but dynamic, background space-time corresponding to the formation of a four-dimensional Schwarzschild black hole by the gravitational collapse of matter in asymptotically flat space.
and in [4]:
As word of his calculation began to spread, Hawking published a simplified version of it in Nature... However, even at this stage Hawking was not certain of the result and so expressed the title as a question, "Black hole explosions?" He noted that the calculation ignored the change in the metric due to the particles created and to quantum fluctuations.
In reality, we expect the influence to go both ways, so that the black hole loses mass as it evaporates. We can (and Hawking did) try to account for the black hole's mass-loss in a kind of "semiclassical" approximation in which we artificially decrease the black hole's mass according to a kind of "average" amount of radiation that it has emitted so far; but that approximation is not self-consistent, as explained in a blog post by Luboš Motl [5].
To really understand what happens when a black hole evaporates, we need to use a theory of quantum gravity. Heuristically, if the spacetime metric is influenced by quantum fields, which can form quantum superpositions, then the spacetime metric itself will be forced into quantum superpositions (very heuristically), so we need to use a theory of quantum gravity to really understand what's happening when a black hole evaporates. This is still an active area of research today.
Edit: I forgot about this...
In a comment, Dvij Mankad kindly reminded me of another line of research that calls into question the assertion that we need a full theory of quantum gravity to resolve the info-loss paradox. I'm not qualified to review that recent development myself, but it is reviewed in [6]. Here's an excerpt from section 1.4.5, where "IR" (infrared) is slang for "very long wavelength phenomena":
Although I did not start this IR project with black holes in mind, as usual, all roads lead to black holes... The IR structure has important implications for the information paradox... This paradox is intertwined with the deep IR because an infinite number of soft gravitons and soft photons are produced in the process of black hole formation and evaporation. These soft particles carry information with a very low energy cost.
References:
[1] Marolf (2017), "The Black Hole information problem: past, present, and future," https://arxiv.org/abs/1703.02143
[2] Mathur (2012), "Black Holes and Beyond," https://arxiv.org/abs/1205.0776
[3] Kanti and Winstanley, (2014),“Hawking Radiation from Higher-Dimensional Black Holes,” https://arxiv.org/abs/1402.3952
[4] Page (2004), "Hawking Radiation and Black Hole Thermodynamics," https://arxiv.org/abs/hep-th/0409024
[5] Luboš Motl (2012), "Why "semiclassical gravity" isn't self-consistent," https://motls.blogspot.com/2012/01/why-semiclassical-gravity-isnt-self.html
[6] Strominger (2017), "Lectures on the Infrared Structure of Gravity and Gauge Theory," http://arxiv.org/abs/1703.05448