Jonathan Blow gave a tech talk at GDC about how the rewind mechanic was implemented. It turns out that he does in fact save the non-constant game state of every frame. Around 6:20 is where he talks about it. https://www.youtube.com/watch?v=tSeYShR-OG0