The way i do it is to save only the player input, and make the game so that it depends only on the player input. (You can introduce some randomness into the game, as long as you do stuff like save the seeds.)
I'm pretty sure this is how most mainstream games do it.
Basically, when the game is played, it records the player's input. To watch the replay, the game is restarted with the same initial conditions, and the control is read from the recorded input file, so the computer "plays" the game in exactly the same way as the human player did.
It can be a bit of a pig to get right- miss out one tiny thing, and the replay diverges from what was recorded.