How can I learn the insane art of 4K democoding?

compression algorithms obviously feature heavily, as do short mechanisms for indexing large amounts of data and a deep knowledge of the available libraries on the target system. (That stuff can just be linked in.)

If I were you, I'd start by reverse-engineering your favourite 4k demos; perhaps starting with ones from 7-10 years ago, and working forwards to follow the state of the art as it progresses. Analysing your compiler's output is a good place to start, too, though they tend to optimize for speed rather than for space.

Techniques for embedded programming may also be helpful, given the constraints they operate under regularly.

In the meantime I have found a great website dealing with 4K coding:

IN4K

Might not be quite what you're looking for, but in the same spirit: There are several Java 4k contests. The objective being to create a Java demo or even game (!) that completely fits into a single JAR of max 4096 bytes.

See e.g.

http://www.mojang.com/notch/j4k/l4kd/

or

http://javaunlimited.net/contests/java4k.php

One might argue that Java makes it much easier (since you can use the whole runtime), but it's still impressive (and you are cross-platform and don't need to learn assembler ;)).

Inigo Quilez has some examples of 1K and 4K intros. You can learn a lot from them. Check out his other articles too.

The article on Tiny PE by Alexander Sotirov is interesting too.