Indeed, this an artform, although a very technical one. There is whole subculture producing similar stuff, though this one is exceptionally good.

About 4k coding, there are a few (mostly independent) aspects. These intros are written in either assembly or C (in the latter case you need to discard the standard libraries). Personally I believe in asm, but not everybody agrees. They are compressed with executable compressors, the best one is crinkler. For the sound, you have to write a simple software synth; you can use different synthesis methods, for example the virtual analogue way (starting with harmonic-rich waveforms like the sawtooth, and sculpting them with filters) works very well. (There are people using general midi samples, but that's just lame :). For the graphics, they use either DirectX or OpenGL, though DX is definitely better in this case, since it will result in more compact code (the API is organized differently). The best 4ks today, including this one, typically runs almost entirely in the GPU, so it's just a tricky big fat shader; this again results in size reduction (at least with DX). All this apply to the recent years; the technologies change over time, and the whole 4k intro business got popular back around 1994. You can find most existing 4k-s on pouet.net.

There are a few tutorials and source codes on the net, but they are neither up-to-date nor very good, I'm afraid. But I found this wiki about the subject which seems to contain a wealth of information.