Probably worth checking out Halo’s theatre mode too, as I think they might use a model like the one I described.
Notice that you can’t rewind the game as you would a videotape, you can only skip backwards in increments.
You also can’t skip forward until you’ve played up to that point (if I remember correctly), and even then you can only skip up to certain points in the game (you can’t just arbitrarily skip forward 10 seconds).
That would be consistent with saving the game state periodically, and just accumulating differences in between.