According to general relativity, black holes are nearly featureless. Specifically, there is a result known as the "no-hair theorem" that states that stationary black holes have exactly three features that are externally observable: their mass, their electric charge, and their angular momentum (direction and magnitude of spin). There are no other attributes that distinguish them (these additional properties would be the "hair"). It follows that if two black holes are exactly identical in mass, charge, and angular momentum, there is no way, even in principle, to tell them apart from the outside.
This in and of itself is not a problem. As usual, problems arise when the principles of quantum mechanics are brought to bear in circumstances where both gravity and quantum phenomena play a large role. At the heart of the formalism of quantum mechanics is the Schrödinger equation, which governs the time-evolution of a system (at least between measurements). Fundamentally, the evolution may be computed both forwards and backwards in time. Therefore, at least the mathematical principles of quantum mechanics hold that information about a physical system cannot be "lost", that is, we may always deduce what happened in the past from the present. This argument does not take the measurement process into account, but it is believed that these processes do not destroy information either. Black holes provide some problems for this paradigm.
However, it may seem that information is lost all the time. If a book is burned, for example, everything that was written on its pages is beyond our ability to reconstruct. However, in principle, some omniscient being could look at the state of every particle of the burnt book and surrounding system and deduce how they must have been arranged. As a result, the omniscient being could say what was written in the book. The situation is rather different for black holes. If a book falls into a black hole, outside observers cannot recover the text on its pages, but this poses no problem for our omniscient being: complete knowledge of the state of all particles in the universe includes of course those on the interior of black holes as well as the exterior. The book may be beyond our reach, but its information is still conserved in the black hole interior.
The real problem became evident in 1974, when physicist Stephen Hawking argued for the existence of what is now known as Hawking radiation. This quantum mechanism allows black holes to shed mass over time, requiring a modification to the conventional wisdom that nothing ever escapes black holes.
The principles of quantum mechanics dictate that the "vacuum" of space is not truly empty. Transient so-called "virtual" particles may spring in and out of existence. Pairs of such particles may emerge from the vacuum (a pair with opposite charges, etc. is required to preserve conservation laws) for a very short time; due to the uncertainty principle of quantum mechanics, short-lived fluctuations in energy that would result from the creation of particles do not violate energy conservation. In the presence of very strong gravitational fields, such as those around a black hole, the resulting pairs of particles sometimes do not come back together and annihilate each other (as in the closed virtual pairs above). Instead, the pairs "break" and become real particles, taking with them some of the black hole's gravitational energy. When this occurs on the event horizon, one particle may form just outside and the other just inside, so that the one on the outside escapes to space. This particle emission is Hawking Radiation.
Theoretically, therefore, black holes have a way of shedding mass (through radiation) over time. Eventually, they completely "evaporate" into nothing! This process is extremely slow: black holes resulting from the collapse of stars may take tens of billions of years (more than the current age of the Universe!) to evaporate. Larger ones take still longer. Nevertheless, a theoretical puzzle remains: if the black hole evaporates and disappears, where did its stored information go? This is known as the black hole information paradox. The only particles actually emitted from the horizon were spontaneously produced from the vacuum, so it is not obvious how these could encode information. Alternatively, the information could all be released in some way at the moment the black hole evaporates. This runs into another problem, known as the Bekenstein bound.
The Bekenstein bound, named after physicist Jacob Bekenstein, is an upper limit on the amount of information that may be stored in a finite volume using finite energy. To see why this bound arises, consider a physical system as a rudimentary "computer" that stores binary information (i.e. strings of 1's and 0's). In order to store a five-digit string such as 10011, there need to be five "switches," each of which has an "up" position for 1 and a "down" position for 0. Considering all possible binary strings, there are therefore 25 = 32 different physical states (positions of switches) for our five-digit string. This is a crude analogy, but it captures the basic gist: the Bekenstein bound comes about because a physical system of a certain size and energy can only occupy so many physical states, for quantum mechanical reasons. This bound is enormous; every rearrangement of atoms in the system, for example, would count as a state. Nevertheless, it is finite.
The mathematical statement of the bound gives the maximum number of bits, or the length of the longest binary sequence, that a physical system of mass m, expressed as a number of kilograms, and radius R, a number of meters, could store. It is I ≤ 2.5769*1043 mR.
This is far, far greater than what any existing or foreseeable computer is capable of storing, and is therefore not relevant to current technology. However, it matters to black holes, because if they hold information to the moment of evaporation, the black hole will have shrunk to a minuscule size and must retain the same information that it had at its largest. This hypothesis addressing the black hole information paradox seems at odds with the Bekenstein bound.
In summary, there are many possible avenues for study in resolving the black hole information paradox, nearly all of which require the sacrifice of at least one physical principle. Perhaps information is not preserved over time, due to the "collapse" of the quantum wavefunction that occurs with measurement. Perhaps there is a way for Hawking radiation to carry information. Or possibly, there is a way around the Bekenstein bound for evaporating black holes. These possibilities, as well as more exotic ones, are current areas of study. Resolving the apparent paradoxes that arise in the most extreme of environments, where quantum mechanics and relativity collide, would greatly advance our understanding of the universe.
Sources: https://physics.aps.org/articles/v9/62, https://arxiv.org/pdf/quant-ph/0508041.pdf, http://kiso.phys.se.tmu.ac.jp/thesis/m.h.kuwabara.pdf, https://plus.maths.org/content/bekenstein