How black holes encode or destroy information is an open question, which RichS touched on. However, while he provided an answer consistent with the No Hair Theorem, I will provide an answer derived from the holographic principle. I'd like to stress that both are equally valid, since we (as of yet) do not know enough about black holes.
In terms of the holographic principle, the information about the matter that formed the black hole is encoded in some manner (micro gravitational fluctuations maybe?) on the two-dimensional 'surface' of the event horizon. It has been theorized that one could reconstruct this information by measuring the outgoing Hawking radiation, since this process decreases the radius of the black hole, hence the surface area of the event horizon, and subsequently the amount of information. I would liken this to burning a book and then trying to reconstruct the book by measuring the properties of the ashes and radiated light.
When two black holes merge, they form a black hole of smaller mass than the combined masses. Once more the total surface area of the event horizons has decreased to that of the event horizon of the new black hole, so information must have been 'radiated'. Black hole-black hole mergers are not believed to have any optical counterpart (burst of light for sake of simplicity) and the merging process is derived from relativity, so Hawking radiation is not a component of consideration. Where could the information have gone? Well, luckily enough these mergers do radiate gravitational waves, now proven by LIGO's recent discovery. Thus the information, if it does in fact encode itself on the event horizon surfaces, could be radiated/lost by the gravitational waves created during the merger.
EDIT: The above description sounds very 'hand-wavey', so I will expand on proposed theoretical method behind it.
Gravitational radiation is generated by the changing quadrupole moment, caused by the two in-spiraling black holes. However, just as for the case of electromagnetic radiation emitted by oscillating charges, the quadrupole moment contribution is only one part of the greater multipole expansion of the oscillating masses. Oscillations of the the event horizon would then cause deviations of the system from the simple quadrupole approximation, and result in gravitational radiation from the high-order multipole terms. This radiation falls off with distance faster as one moves to higher-orders, making measurement of these contributions much more difficult.
Of course this is just one proposed solution to the black hole information paradox.