Attaining undo/redo functionality with Immutable and a Flux implementation is basically trivial. This is in part due to the value-passing made possible by Immutable and in part because of the in-browser/in-memory nature of using Flux.
Conceptualizing this in terms of Relay-GraphQL mutations, however, is not obvious. Are there any known patterns out there that simplify this?
Relay can't (yet) do local state. So your option at the moment is to a) store "drafts" of changes in a Flux store or b) create a draft type that you continually create new versions of via a mutation. You could track the new draft ids in the client and "undo" by reverting the active draft id.