Eu não conheço profundamente mas sei em linhas gerais.
Temos comportamentos e estados. Ou seja, algoritmos e estruturas de dados. Comportamentos são inerentes à aplicação e não mudam. Estados existem durante a execução, e portando eles mudam.
O que o depurador histórico precisa fazer é tirar uma fotografia (snapshot) do estado sempre que ele mudar. Com o registro de todas mudanças de estado você pode ir pra frente e para trás.
Pense em projetor de slides (se não sabe o que é isto, pense no PowerPoint). Os slides são esses estados, você pode ver o próximo ou pode voltar para os anteriores. Obviamente que o próximo pode depender de uma execução de um passo do algoritmo para provocar mudanças de estado, assim como já funciona no debugger normal.
Tendo todos registros basta restaurar para o ponto que deseja. Pode inclusive dar um replay de todos.
Então nem parece tão complicado assim. Ainda que também não seja tão simples quanto descrever aqui.
Complica um pouco mais com estado externo à memória. Você não pode simplesmente acessar o estado externo novamente, nada garantirá que o resultado será o mesmo. Na verdade tem boa chance de não ser. Então precisa gravar estes estados também. Para restaurá-los complica porque o código tentará acessar o recurso externo, só que se você "voltou na história" tem que injetar o dado gravado no lugar da requisição real.
Pode se tornar impraticável gravar toda mudança de estado. Então isso ocorre seletivamente. Nem todo estado e nem toda mudança é gravada.
Você pode inclusive pegar o arquivo gerado por ele em uma máquina e fazer o replay em outra máquina.
Ele ajuda, mas não faz milagres.