Information is Never Lost?

Here's the latest installment in my apparent inability to understand the technical concept of information.

In an interview with Leonard Susskind, in which he recounts a famous dispute with Stephen Hawking, Susskind says:

Stephen Hawking once said something about black holes that apparently upset you. What was it?

Stephen said that when a bit of information falls into a black hole it is permanently lost to the outside, despite the fact that he also proved that black holes evaporate and eventually disappear. That claim touched off a crisis in physics, a clash of basic principles like no other since Einstein was young.

The problem that upset me is that the most basic principle of physics—the principle that underpins everything including classical physics, thermodynamics, quantum mechanics, energy conservation, that physicists have believed for hundreds of years—is that information is never truly lost. It can be scrambled beyond recognition, but it is never completely erased.

Hawking's claim was outrageous, but he had very good reasons for it. So good that it took more than two decades to figure out why he was wrong. And the question led to a tremendous paradigm shift in the way we think about space, time, matter, and bits of information.

But if information is "scrambled beyond recognition" isn't it lost? Maybe there's a difference between theoretically lost and practically lost.

What happens when a library burns down? Is Susskind saying that all the information written on all the pages is theoretically reconstructible from the ashes?

And Stephen Pinker is no mathematician or physicist, but I liked the definition he gave in How the Mind Works:

Information is a correlation between two things that is produced by a lawful process, as opposed to coming about by sheer chance. We say that the rings in a stump carry information about the age of the tree because their number correlates with the tree's age. The older the tree, the more rings it has. And the correlation is not an accident, but is caused by the way trees grow. Correlation is a mathematical and logical concept. It is not defined in terms of the stuff that the correlated entities are made of. Information itself is nothing special. It is found wherever causes leave effects.

So if information is the remnant of a causal relationship, then how is it that information is never created? Aren't there new cause/effect relationships happening all the time? In Pinker's tree example, isn't novel information being created as the tree grows and creates more rings? If information is simply being transformed in this case, what is the transformation?