BRAID is very well executed. I've done a game with the ability to rewind time and I can say that simply storing the positions/orientations of your objects is not enough. There are many other things to remember. Here's a couple:
- Random number generation seeds (so that if you fast forward all code using random numbers will get the same results and produce the same effect).
- Internal states for objects (e.g. going forward your character is in the RUNNING state, you then rewind, but forget to set him back to STANDING, now when you go forward again he's in a different state than he was originally).
If I were going to do it again I would design my game to be extremely Object Oriented (i.e. very few structs). I would then have all of my objects implement some sort of serialization scheme so that I could simply at the end of each frame ask everything important to serialize itself into a buffer. I could then compress this buffer in memory for later restoration.
I would also design all of my gameplay to not be reliant on things happening in order. I.e. it should not be a problem to instantly set my character to the RUNNING state, the logic should not require him to be in the STANDING state before I can set him to the RUNNING state. This would allow extreme flexibility, and allow me to have a buffer of arbitrary length (I don't have to worry about something important falling off the back of the buffer).
As long as you know you're going to do it, then it's not too bad as long as you design your game well.
IMO one of the things Braid did excellently is the reversal of their audio. You don't usually see that in games that allow you to rewind time.