I do not know deeply but I know in general terms.
We have behaviors and states. That is, algorithms and data structures. Behaviors are inherent to the application and do not change. States exist during execution, and by porting they change.
What the historical debugger needs to do is take a snapshot photo of the state whenever it changes. With the record of all state changes you can go back and forth.
Think about slide projector (if you do not know what this is, think about PowerPoint). The slides are these states, you can see the next or you can go back to the previous ones. Obviously the next one may depend on a one-step execution of the algorithm to cause state changes, just as it already works in the normal debugger .
Having all records just restore to the point you want. You can even give everyone a replay .
So it does not even seem so complicated. Although it is not as simple as describing it here.
Complicates a bit more with external state to memory. You can not simply access the external state again, nothing will guarantee that the result will be the same. In fact you have a good chance of not being. So you need to record these states as well. To restore them complicates because the code will try to access the external resource, but if you "went back in history" you have to inject the recorded data instead of the actual request.
It may become impractical to record any change of state. So this happens selectively. Not every state and every change is recorded.
You can even get the file it generates from one machine and replay another machine.
It helps, but it does no miracles.