It is actually a good question that challenges what physicists mean when they talk about information. What you're referring to is called the Black Hole Information paradox, so a good place to begin in your understanding the wild statement is the Wikepedia pages on this and related topics.
There was recently a discussion of this selfsame topic at Why is information indestructible? and my own answer is https://physics.stackexchange.com/a/71346/26076, but I ended up going into more detail there than I wanted to owing to questions on my answer. So here is a summary.
Most of the laws of physics are reversible, which means that they are the same whether time runs forwards or backwards - there is one exception to do with CPT violation but that's not my field and I understand that it doesn't really bear on the present problem, so for the purposes of this answer take the laws of physics to be reversible. If you hearken back to high school / first year mathematics, a function is invertible if and only if it is one-to-one and onto. If we take a set of things $X$ (to steer clear of complexities, let $X$ be finite), together with a specification naming one special thing $x_0\in X$ in that set, then that specification is the information identifying our special thing. This information is not in theory changed if we instead know the image of that thing $f(x_0)\in Y$ under an invertible function $f$ that maps the set onto another set $Y$, because we can in principle compute $f^{-1} o f(x_0) = x_0$ - in practice this is not always possible: cryptography allows one to "hide" this information through making $f$ very hard to invert unless one has the explicit rule for $f^{-1}$, but the information is always there, as someone who does hold the cryptographic key can show.
It's the same problem with the laws of physics and the evolution of a system's state. The sets $X$ and $Y$ are unimaginably big and the full specification $x_0$ of a system's state at any one time likely requires an unimaginably big amount of information (say a huge book defining the states of all the quarks, gluons, photons, .... making the system up). But in principle many physicists believe that the laws of physics are truly reversible: one and only one possible state $x_0$ in $X$ is mapped onto each state in $f(x_0) \in Y$ where now $f$ is the transformation wrought by the laws of physics. So that if one could feed the exact specification into a simulation of the system, one could run it forward or backwards in time and calculate what the system's state is like at all other times (let's just stick with pure quantum states here or with classical states, so that we don't get into fights over the quantum measurement problem). You could in principle feed an exact specification of the state of all the constituents of the smoke and run a simulation of the laws of physics backwards in time to find the system's state before the fire and read the Bible or the Kama Sutra, whichever it was that was defined by the system's earlier time state.
All of this goes up in smoke, forgive my choice of words, if two or more beginning states in $X$ are mapped to the same ending state in $Y$. We cannot then tell from a specification of $y\in Y$ what the beginning state was that evolved into $y$, because there are several possible candidates.
To illustrate the above, you may not know that there is one physical system that indeed does a baby version of the wild claim you quote. It's a little less sensational, but it
may still surprise you. This is the phase conjugate mirror.
Suppose we have a lightfield (imagine the Mona Lisa encoded as a hologram) at some plane represented by $\psi(x,y)$ that is input into a turbulent medium, with optical inhomegenities swirling around in it, so that, after going some distance $L$ through the medium, the Mona Lisa is now $T(0, L) \psi(x,y)$ and has been utterly scrambled and rent unkennable by the sheer complexity of the random transformation $T(0, L)$. Now at the output of the medium, one can, through the use of clever nonlinear optics, reflect back the complex conjugate of the light field $(T(0, L) \psi(x,y))^*$ into the medium. It so happens that Maxwell's equations have a structure such that this complex conjugate is the field that one would see at the output if one began with the original field $\psi(x,y)$ propagating in the opposite direction at the medium's input and ran the evolution back in time to the point where the image were at the output. Like all the laws of physics, Maxwell's equations can be "run backwards in time" i.e. define reversible transformations on their input state. So, what happens now is that $T(L,0)$ imposed on the phase conjugate reflected field as it is reflected back through the same medium inverts the original random transformation and the original unscrambled Mona Lisa appears back at the output. We have, through the phase conjugate mirror, inverted a fantasticly complex transformation. The catch is the optical time of flight must be short enough that the medium does not shift. Therefore, the phase conjugate propagation can "see" the exact state of the medium as the image propagates and thus use that state information to correctly unscramble the image. The principles of what is going on here are a little easier to see with the picture below, which I took from the Wikipedia page on Nonlinear Optics. In the top sequence, the bottle distorts the tigercub's image and the phase conjugate image is reflected back into the same bottle. The phase conjugate image is the lightfield that we would get if we took the right-to-left running field defining the tiger's image and ran Maxwell's equations back in time to find the field that would have begotten the first before it went right-to-left through the bottle. The forward and backwards transformations thus unscramble the image. In contrast, the lower sequence of forward and back propagation just imparts the distortion of the bottle, then the distortion of the bottle's mirror image.
Your fire is in principle just a more complicated version of the scrambling optical medium and Nathaniel's answer simply describes the analogue of phase conjugation that would apply to the burnt book system.
I like to summarize the above thoughts by saying: no matter what evolution the World undergoes, if the laws of physics are reversible, then the World in principle must remember how to get back to any former state.
In closing, what the Black Hole Information Paradox is about is that it seemed many years ago that black holes could encode very little information: their state was thought to be wholly determined by their Schwartzschild horizon radius, their spin and their electrostatic charge. That's essentially three real parameters: not much memory space wherein to encode the unimaginably complex makeup of whatever one throws into the black hole. Therefore, if so, we seem to have found an example where we have an essentially irreversible situation even in principle: all of the fantastically many possible states of the swallowed matter and energy system are mapped to a few real numbers. The debate about this paradox therefore has to do with how really do we have to encode a black hole's state, and more generally how Nature encodes all system states and some theorists, notably Leonard Susskind believe now that black holes are much more complicated things that can encode the states of whatever is thrown into them.
