A sprite and an array in a container works for this. Here's an example:
http://dl.dropbox.com/u/5426011/examples16/mario_record.capx
Notice that only two events are used for the recording and playback. The rest are just standard game events.
This idea can be extended by adding some interpolation between recorded states to smooth out hiccups caused by garbage collecting or other programs running in the background.
R0J0hound your example made me wonder how is possible to port from CC to C2, i've ported some .cap to .capx but the results were not perfect.
The one what im trying to port was Braid's time rewind, isn't possible for HTML5?