Can anyone explain how these tools work? How are they recording program execution? Don't they need to keep track of every register, memory address and such? Seems rather complicated.
Tracking the effects of every instruction does is likely to give you a simpler implementation (since you just repeatedly say "next instruction, now what did that do?") but it's quite slow and can be hungry on memory, since you have to log every change.
More sophisticated record/replay/reversing tools like rr provide a more sophisticated backend that doesn't need to track state per instruction. They can be much faster - and consume less memory - but more coding is required to make sure you're tracking the right state, efficiently.