It's tricky to do. Here are my notes on what I do for my level editor Undo/Redo. It is working out pretty well.
I have two variable size 1D arrays which act like stacks/queues when convenient: ChangeLog() and RedoLog()
They both start out empty and are dim'd with using the same type which has enough info to hold Old/New states for tiles.
Whenever the user does an action on a tile in the editor I log it in ChangeLog()
If the user hits CTRL-Z I do the following:
- Undo the change on the map by replacing the New tile with the Old tile from ChangeLog()
- Take it out of ChangeLog()
- Put it onto RedoLog()
If the user hits CTRL-Y I do the following:
- Redo the change on the map by replacing the Old tile with the New tile from RedoLog()
- Take it out of RedoLog()
- Put it onto ChangeLog()
When the user does an action in the editor I clear RedoLog()
The idea is you cannot redo steps once you've "broken the chain" of events.

A 3D marble platformer using Newton physics.