You can find most of entropy of black hole on the surface of Event Horizon associated with strings. The rest is associated with Hawking Radiation etc. As region inside event horizon is fully disconnected from our universe, this must be true to prevent "entropy decrease" of system (our universe).
The same duplicate entropy can be found inside event horizon, too. But, the most of entropy is found at the singularity.
How can you pack so much information in such a small region?
Actually, its nothing in front of singularity seed of big bang. There's no limit to the process of packing.
How does the packing works?
We don't know yet. Remember, when a theory gives you monstrously high or low number like infinity etc, it means it has failed to describe the situation in our working domain. When General Relativity predicts singularity, it means describing singularity is beyond its level. General Relativity is for big bodies and singularity is very very small where probability rules. So, to understand the process, we need a theory of gravity for quantum world. And, we are working on it.