[fluoridation]

Yes, that's what it means. Ideally you'd record the state of memory and CPU after each instruction. In practice you can take snapshots at regular intervals and hook system functions to record their inputs and outputs. If a call has to be replayed the debugger intercepts it and gives the debuggee a recorded result.

[greglaw99]

Exactly. Except there are sources of non-determinism other than syscalls. Namely asynchronous signals, thread ordering, shared memory and non-deterministic instructions. They can all be dealt with though.