Maintain a list of user actions and allow users to reverse selected actions.
Each 'action' the user does is recorded and added to a list. This list then becomes the 'history of user actions' and users can reverse actions from the last done action to the first one recorded. This is also called a Linear Multi-level Undo.
Interacting with the history
There are two variations on how to show the history of actions to the users. First there is the standard 'office-like' way where the 'Edit' menu contains both 'Undo' and 'Redo' functions with their keyboard shortcuts. Often there is also a widget in the toolbar that can show the last items in the history. By dragging the selection in the list, actions can be undone. A second variant is to work with primarily with the history list itself and moving a slider or scrollbar to move back in history and undo actions. Photoshop uses such a variant.
Actions in the history are usually displayed using a text label such as 'Create circle', 'Typing',' New contact'. Such labels only name the function and not the object the functions work on. In some applications it may be better to include the object and the parameters as well, for example 'Change-color Circle12 to Red'.
Granularity of actions
When designing Undo it is important to determine the desired granularity of actions. For example, it is usually not desired to record each key press in a text editor as an action. Instead, typing a word is used as a unit of action. Designers need to determine what unit of action is appropriate in the application.
Although most actions in the application may be reversible, it is very likely that some actions will not be reversible. For example, printing, saving, doing a payment, or downloading an object. For actions that are non-reversible and 'negative' of nature (like paying or destroying something), need to show the user a Warning Message and not add the action to the history.
In some cases, it can be meaningful to allow single actions from the history to be deleted. This is the case when a certain 'episode' of work must be deleted or undone while keeping work that has been done later on. Selective undo is conceptually much more difficult than linear undo since there is a notion of 'dependency between actions' that determines the consequences of undoing a particular action. For example, if a 'create circle' action is undone at some point in the history, subsequent actions in the history working on that object loose their meaning and must be deleted. There are many semantic issues with selective undo, see Berlage (1994) for more information on selective undo.
Object-based Undo can sometimes be considered as an alternative to Selective Undo. With Object-based Undo, each object has its own action history. Upon selecting the object, the users can undo actions done on the object. Naturally, this requires the application to have a clear concept of an 'object' and is therefore not applicable for bitmap editors. See Zhou and Imamiya (1997) for more on Object-based Undo.
If the application is a multi-user application and uses undo, the application must distinguish between local actions and global actions. That leads to multiple histories and requires special semantics for what happens when undoing actions. See Abowd and Dix (1992) and Sun (2000) and Ressel and Gunzenhouser (1999) for more on multi-user undo issues.