I have no idea how walaber does it.
But.. i can speculate that he did it one of two ways:
1) Don't record a video at all. Instead, record something like a script, or keystrokes, or motions, and play back a scene according to that (these are how alot of games do scripted scenes).
2) Record screenshots to file.. or even better, grap the contents yourself, and start combining frames into a fast (and not heavily compressed) encoding codec (ie. not mpeg, divx, or theora) - and stream to disk. Then, to playback, just start playing back your codec.
Encoding to a real format like theora, mpeg, divx, etc at runtime is too slow - which is why fraps encodes video into a not very compressed file.You can later go back and compress it with something like theora.