Probably the same as a normal text undo. You store the "actions" the user performs against the document on a stack. Each action is a replacement of one text string in the document with another (where strings can be zero-length and can start and end at any point).

Actions can "do" and "undo" themselves against the document trivially. Then to save space, you compress adjacent actions into single actions (e.g. add('a', 0) and add('b', 1) compress to add("ab", 0)).

I wouldn't be efficient wrt space to keep copy of every version of the file. Instead I suppose they keep the actions of the writer(s).

Algorithmically it shouldn't be complicated. Maybe they just keep history of what happened in the environment and reproduce it. Maybe they even have some checkpoints saved so that there is no need to reconstruct it from the beginning every time. And maybe they can compress events. Instead of: (type a),(type s),(type k) they have just (type ask) and in case you want better granularity they have it recorded somewhere.