Question

How does procedural generation work?

Answer 1

It's a pretty broad term. In many ways that depends on what you want to generate - essentially it means to use an algorithm to generate data that fits certain criteria you're looking for, instead of providing the data a priori.
One of the simplest examples for procedural generation would be random noise. For 2D data (like images) there are a variety of methods for generating patterns. Using several octaves of Perlin noise blended together by various blend functions can give really interesting results resembling natural patterns like clouds, marble, or wood. Any synthesizer would be considered a procedural generator, in this case for data that is used as sound.

Answer 2

What if I want to do stuff like the below program? (it's this demo if you can't run it: http://www.youtube.com/watch?v=oOKE8vcf9w4 )

Answer 3

and it's all done in 64 kilobytes! 64!!!!

Answer 4

A lot of the textures they use for the space/galaxy style scenes in the beginning look like Perlin noise to me. The 3D models are primarily beveled rectangular prisms (which are also relatively easy to generate in code) and tubes that seem to be extruded along a set of splines. So, you come up with a set of animations (like translating a quad towards the camera), generate a bunch of quads that follow those paths, and texture them with a texture you generate from Perlin noise in code. Similar for the 'monoliths' - generate one, then some 3D function (a couple of overlapping sines, for example) that you let a few dozen instances of them move along. For the tubes, use another set of 3D functions and extrude a circular cross section along the function to generate a mesh. For audio, demos like this often use a tracker (sequencer like application that places instruments in multiple channels along a time line) and a realtime software synthesizer that can represent the sounds with a few parameters to an algorithm.
This is all a gross simplification, of course, and getting something like this in <64KiB is still an impressive feat to be sure - but methods like the above are at the core of it all.
It's all about finding the math and algorithms that you can use to generate the data (meshes, textures, animations, sounds) that you want to display.