How it is possible? Silly question! Think of what you can do with a C64 that has the same amount of memory and how much people spent on doing details in the code, music and gfx to make stuff work. Add to this a much faster computer, 3D graphics capabilities out of the box, same with sound... (sort of, they have their own soft synth written by kb).
It takes tons of time planning and implementing the thing, but it is far from impossible. The real problem is that people don't worry about code size anymore beacuse we don't
have to---so the quantum leap from getting the idea to actually do the thing is what amazes me. As things are now with fb, they have made a demo-editor, that makes it more or less easy to make these demos.
If you want to see more amazing demos in 64KB check out
http://www.pouet.net - especially AND's intros (squish and zoom3) and recently Point Blank made by Stockholm Syndrome.