The first thing to understand is that we have no actual knowledge of how information and black holes interact.
What we do have are theories that are well supported by experiment (General Relativity, which predicts Black Holes but which says nothing about information) and Quantum Mechanics (which says a lot about information (in this technical sense) but nothing about BHs.) We also have a variety of theories, none of which have any substantial experimental support, and all of which are incomplete (which means we don't know if there's actually a viable theory there -- all we have today is bits and pieces that look promising). One of the goals of all of these theories is to -- somehow -- meld GR and QM into a single coherent theory with greater explanatory power than the two separately.
It is very fair to say that some of the work which has been done to date which tries to link information and BHs is plausible and (at least) does not contradict any experimental evidence we have. And some of them (like what Hawking used in the prediction of Hawking radiation) are such a careful application of QM in the GR context that most physicists would be surprised if they turned out to be incorrect.
The bottom line is that GR and QM are both amazing theories which yet cannot be completely correct -- they must both be subsumed in some more encompassing theory. (Or at least everyone is convinced of that. I am too, BTW.)
Due to the mathematical underpinnings of QM and GR, physicists vaguely can see how some generalization of QM might, possibly be able to include GR someday. But virtually no one can see how GR could be extended to include QM. So the smart money -- just about all the money, actually -- is on extending QM in some way.
One of the most basic features of QM is that it is linear and preserves information (in a certain well-defined, but technical sense). If GR could be derived from some extension of QM, we'd expect that that extension of QM preserves information, and that GR also must preserve information.
On the face of it, GR by itself says that information which falls into a BH is lost. Zap. Gone. Never to return. Therefor finding ways to get GR to preserve information may be an important clue to the ultimate combined theory. And extensions of GR which preserve information seem more likely to be correct.
So the paradox is that BHs, which are predicted by our marvelously correct theory of gravity, GR, do not conserve information. But we have reasons to strongly suspect that BH built from the hypothetical gravitational extension of QM would preserve information. Something's wrong here!
One of the plausible theories that have been developed to resolve this says that Hawking radiation -- which seems very plausible, and which carries energy away from a BH in contradiction of vanilla GR -- might also carry the "lost" information away, eliminating the paradox.
Maybe.
But remember that there isn't any experimental evidence for any of this. It's all based on smart hard-working, competent scientists trying to use their brains and their intuition to guess what the undiscovered theory which merges GR and QM will predict and to turn it into consistent math. It's certainly better than a random-assed guess, but it is a far cry from established science.
Keep watching -- I hope that all this work will bear fruit and a real theory with experimental evidence behind it might emerge in our lifetimes.