various laws about our universe (including the conservation of energy, conservation of quantum information, and the no-hiding principle etc...) imply that information can neither be created nor lost.

What is information? It is everything and yet nothing. As I understand it, there is no specific thing which can be defined inherently as "information". Yet anything can be perceived as or used as information. In that sense information is lost all the time, what is never lost is energy/field. It may become more dispersed or change form, thus changing the "information" but the essence and potential for information is never lost.

If you think about it, the idea that information is lost once it falls inside a black hole has some fairly far-reaching consequences. Not least it would essentially disprove some of the most fundamental principles of quantum mechanics. However, even more importantly, it means that if the first part is still true -- that raw information cannot be created -- then eventually black holes will eat all the information in the universe.

Black holes can break down information, but they can't destroy energy or potential information. In the end the black holes (theoretically) will create white holes, and so they will transform the information ultimately rather than destroy it. Information in terms of quantum mechanics is basically a library of potential oscillations and particle positions etc. which means that information changes all the time but the potential for everything that is possible will remain, so in a way information cannot be destroyed specifically because it is always being destroyed as in transformed into new information.