I think the best strategy to make it intuitive would be to flatten the redo stack as a single command, so that the pile of successive 'undo's gets redone as a single step. In your example:

  Type "hello"
  Type "world"
  Type "!"
  Undo
  Undo
  (Editor is "hello", with "world!" on the redo stack)

  Type "dave"
  (Editor is "hellodave")
  (This would normally wipe the redo stack but instead it moves it to the undo stack)

  Undo
  (Editor is "hello")
  Undo
  (Editor is "helloworld!")
  Undo
  (Editor is "helloworld")
  Undo
  (Editor is "hello")

I get what you are saying, but I think it is confusing to refer to a 'redo' stack at all. There is only ever one stack, and you are always at the end of it. To go back through time you copy the states onto the stack (stack isn't even the right word, I guess but I'll stick with it)

Consider typing the alphabet

Stack:

  1.a
  2.ab
  3.abc
  4.abcd

Now you 'undo' back to place 2 and type 'x'. But while you are conceptually travelling back in time, what the stack really looks like now is:

  1.a
  2.ab
  3.abc
  4.abcd
  5.abc
  6.ab
  7.abx

A conventional undo stack would leave you stuck at a new place 3: abx, all redos gone. Undos from that point can only take you back to place 1 or 0. (Just tested this out on OS X TextEdit, it does this). With the linear stack, there is no redo, only undo.

I think that is what the article means at least...

Yeah that's the same thing and is probably how you'd actually implement it, but conceptually you can think of there being an undo and redo stack.

Photoshop has nonlinear history. When this option is tunred on, you can undo several times, make a change, and not lose all the states you've undid - isn't this what he's talking about?

Yeah maybe, I'd have to play around with both to see which is less annoying.