You touch on a very interesting and general concept, and that is the correspondence between lossless compression algorithms and probability distributions, and the subsequent correspondence between probability distributions and procedural generation algorithms.

Consider the first correspondence. Suppose you knew a certain class of strings arose from a probability distribution. Then you can talk about the strings that are most likely to occur, or, more useful in general, about the individual characters that are most likely to occur given a history of previous characters. Using this, you can make a compression algorithm that will map (symbol, probability) or (symbol + history, conditional probability) starting from the highest probability, to the numbers 0, 1, 2 ...

This is arithmetic coding.

http://en.wikipedia.org/wiki/Arithmetic_coding

The result is optimal in terms of expected compressed string length assuming the strings you use this on really do come from that distribution.

Now consider the other way around. Suppose you have a lossless compression algorithm. Find the (uncompressed symbol, compressed symbol) pair (possibly with context) that achieves the highest compression. Assign that a high probability. Then find the next pair. Assign that a slightly lower probability (This can be done in a more principled manner than I'm alluding here). Then you have yourself a probability distribution.

More on data compression theory:

http://en.wikipedia.org/wiki/Data_compression

But what happens once you have a probability distribution over some data type, is that you may cast the problem of automatically generating instance of that data type as sampling from the distribution. Many procedural generation algorithms that give nondeterministic results (and the useful ones do, otherwise the work the modeler has to do is fundamentally the same) can be re-cast as sampling from a probability distribution; look at what the algorithm is generating and learn the distribution.

Note that this is uncomputable in general for the same reason Kolmogorov complexity is. This is known as Solomonoff induction:

http://singinst.org/blog/2007/06/25/solomonoff-induction/

So to answer your original questions:

1. The information (as in information entropy) in the algorithm in the CD is the entropy of the true probability distribution from which your levels originate.

2. And yes, in principle you can use the correspondence between data compression and procedural generation to generate instances of any arbitrary data type, not just 3D game levels. It may be hard to design a probability distribution that will create well-formatted instances though :)