It's just like using Markov chains to make English-like gibberish, but for pictures.
The interesting bit is that (I think) the generative adversarial network is regressing from random noise to an image, which isn't how most autoencoders work.
Despite their simplicity, Markov chains are used throughout modern statistical AI, e.g., the Google Translate language model is essentially a big Markov chain. The fact that deep networks can apparently form better generative models across a wide range of applications (no one has ever actually gotten these kinds of image generation results from Markov chains) means that they really are getting at more interesting structure. They're not a panacea, but it's still a pretty big deal.
Yes and no. The latent representation space can be seen as a kind of result of compression, but the opposite is going on. As you say, these models generate images from (latent space) random noise, but there's no direct mapping from image space to latent space (as there are with autoencoders), so no way to compress, really.
If you insist on a practical way to do it, gradient descent on the latent vector would probably work well given the type of results DeepDream has obtained.