I made a real simple system (it was for a 2D Mobile game) which worked extremely well and only took me a few hours to integrate. This was for a sports game, so for each player on the field they needed an X, Z animation and direction they are facing (among other things, but these were the core stats the needed to be replayed). The player class was already set up like this, so there was no refactoring needed or any headaches when implementing this system.

I had an array (note the int is actually Fixed point) in the Player class,
int m_iReplayPos[NumberOfFrames][2]; where NumberOfFrames = the number of frames to save, and pos0 = X, and pos1 = Z;

In addition, I stored their animation data like this
byte m_ReplayAnims[NumberOfFrames][2]; where NumberOfFrames = the number of frames to save, and pos0 = Direction they're facing (North, south, etc), and pos1 = their animation.

For each frame that was rendered (remember this is a cell phone game so fps = 10->15) i stored the position of each player and their animation + direction (I had a function that when it rendered them, used the animation and direction to display the correct frame).

I did the same thing for the ball and camera, and just iterate through this array when replaying, disabling ALL AI and anything else that would divert from this set course. As i said, it had to be simple for a cell phone game, (which was already pretty simple), but it integrated nicely into our game. In about 2 hours, I had the replay working no problems using about 10k for 15 seconds or so of replay.

Hope this helps!