There’s a lot more that we don’t know about black hole entropy than we do. But to summarize what we do know:
By a classical calculation, since black holes have “no hair”, they ought to have no entropy. This is definitely problematic, since objects with considerable entropy can turn into black holes.
It was noticed early on that certain aspects of black holes are closely analogous to thermodynamic properties. In particular, the total area of the event horizon(s) of a set of black holes never decreases. Thus, it is tempting to conclude that a black hole does, in fact, have an entropy, proportional to the area of its event horizon.
That still leaves the question of the proportionality factor. The obvious choice would be Planck units. And this is supported by Hawking radiation, which can be derived without recourse to thermodynamics, or can be derived entirely from thermodynamics assuming that proportionality, with the same results.
Certainly, the proportionality factor must be very, very large (i.e., a very high entropy per area), because anything at all can form a black hole, and the black hole, being the final state, must have at least as much entropy as its precursor (if the laws of thermodynamics are to hold).
But then there’s the question of how a “hairless” black hole can have any entropy at all, let alone such a high one. The usual answer nowadays is that the no-hair theorem is a purely classical result, and that in a proper quantum theory of gravity, a black hole would have some sort of microstructure in its event horizon that would contain all of the information. But unfortunately, we don’t have a quantum theory of gravity, so we can’t verify that. The String Model sort of predicts it, but then, the String Model can predict absolutely anything if you really set to it.
Personally, I suspect (though this doesn’t even really rise to the level of a hypothesis) that black holes have entropy of a different sort, that doesn’t require a microstate, similarly to how subatomic particles have angular momentum of a different sort, that doesn’t require rotational motion (but which is nonetheless interchangeable with the ordinary sort).