There are two sorts of replay systems That I know of.

1) If you have a deterministic game, all you need to store and replay are inputs (user inputs, frame timesteps, random number seeds, ...).

2) Serialisation / Deserialisation of the game state. Have your objects record and replay their states. In fact, you don;t record the states, but the state changes (many objects won't change).

#1 Is very lightweight, IF IT WORKS! The trick is to have a fully deterministic game, and that in itself can be a problem. Second, if there is a discrepancy, it is very hard to track down what made the game and it's recorded part deviate. And once they deviate by the slightest bit, that's it, game over. Anything as trivial as doing one collision check out of order is enough to send the replay sideways. Detecting deviation for debugging requires you to build hash values of object states (whatever that is, like a ray-traces, messages, ...)

Also, you cannot rewind, step into the game, without having to rollback the simulation to the very start, and replay up to the point of interest. Also, you need to decouple the update, and the rendering, if you do not have a fixed frame timestep, and you want stuff like slow motion.

#2 Requires more code. You need to implement serialisation methods to your objects. Then being able to record changes in game states (if you want to have a small replay buffer). It's not dissimilar in many respects to the Quake3 Networking Model. Instead of sending the game state to a client, you just write it to a buffer, and for replaying, grab the game states from the buffer, do interpolation, effects...

'1' is also a little fragile - if you make a recording with v1.0 of your game then the odds are it won't playback the same under v1.1 of your game. Now if you're just using it for an attract screen then you can rerecord without much hassle, but if your players are expecting to keep their replays between versions then it's probably not the best approach.

It is very, very light on memory though - typically you only have to record a handful of inputs every frame, so you can have quite long recordings without taking up much memory at all.

Depends on what you need to reproduce, but 1) will replay 'exactly' as you recorded, or either it will bomb straight away. The second is more like an approximation of what's going on, and the A.I. and other components are disable (it's a 'pure client', like when you replay a Quake3 demo or observe a Guild Wars battle). If that's all you need, and you already have serialisation (load / save), then it's worth considering.

As said, 1) is very fragile. When your game code changes (anything from A.I., to collision, tiny optimisations even), the inputs will most likely no longer be valid. This is not quite so true for 2), although a change in the data format will invalidate the replay as well.

Both require a lot of work tbh. 1) is to make sure it's 100% deterministic, write debug tools to check on that (record/test hash values made of game data) and everytime you tweak the code, you have to keep it mind if the determinism will stick, 2) is writing all the serialisation and delta-compression methods, which is no small task.

Lots of things can get in the way of determinism, especially if you have a multithreaded system, then I'd be very careful. Obviously the threads will have to be sequenced properly, and that may or may not be part of your engine.

If you are pretty confident that your game can be fully deterministic, 1) is definitely the easiest. It's painstaking work (debugging notably), but it's still way more lightweight than 2) which will be a monster.

BTW, if replays are not 100% required and part of the deliverables, then gladly walk away. They are a pain, trust me on that (I've worked on / with a few).

Here's a couple of Gamasutra articles worth checking out:
Instant Replay : Building a Game Engine with Reproducible Behavior
Developing Your Own Replay System

(sign-up is free)

Those articles are pretty much bang on.