"black hole hair loss paradox"
The black hole information loss paradox really shouldn't be called that way. The word "information" in this context doesn't mean what most people (even in physics) thinks it means. All it means is that the process seems to be fundamentally irreversible: You cannot infer the initial state of stuff that formed the black hole from the final state.
This paradox is closely linked to the "no hair theorem" which says that black holes are fully described by merely three quantities: their mass, angular momentum, and electric charge. This means regardless of what you form a black hole from, in the end you have only three numbers.
These three numbers do not contain sufficiently many (beware) details to infer the initial state in its entirety. In this context, physicists often use the word "information" but it's not "information" in the sense that the word is often used specifically to, say, refer to the information content of a bit string or such. This is not what the word means here.
It's a paradox because all other processes in nature are reversible in principle. Of course in reality there are many processes which we never see reverse (burning a book, breaking an egg, etc). But if our current laws of physics are correct, you could reverse them in principle, if you looked for all the particles and did a calculation to find out which places they were in originally etc.
With a black hole you can't do that, not even in principle.
Now, so long as a black hole is just sitting around it's not a huge problem because you might say, well, maybe the details are all inside and we just can't see them.
But along came Stephen Hawking and showed that black holes don't keep sitting around eternally. They decay into random radiation whose properties are entirely determined by the same three variables that determine the black hole geometry.
So, the details don't go into the radiation. At least they don't in Hawking's calculation. This means the process is fundamentally irreversible and in conflict with all other laws of nature, in particular quantum mechanics.
To make a long story short, most physicists think there is something wrong with Hawking's calculation and all those details about what formed the black hole do go into the radiation. They just argue about how that's supposed to happen...
Basically I think it would better be called the "Black hole irreversibility paradox" or maybe the "black hole hair loss paradox".