How is the undo tree used in Vim?

This answer says:

Vim's undo/redo system is unbeatable. Type something, undo, type something else, and you can still get back the first thing you typed because Vim uses an undo tree rather than a stack. In almost every other program, the history of the first thing you typed is lost in this circumstance.

This is the first I hear of this. How can I backtrack along the tree?

See also :h undo-redo, which lists all the commands and their usage.

There are two ways to traverse the undo tree. One is to go "back in time". g+ and g- will traverse all of the nodes in the tree in chronological or reverse-chronological order (which can be a bit confusing, because it can jump arbitrarily between undo branches, but if you do g- long enough you'll always get where you need to go eventually). :earlier and :later take a time descriptor like 7m or 1h; again this can jump you arbitrarily between undo branches.

The other way is to jump to specific nodes in the tree using :undo n where n is a number of an action. (All actions, i.e. text additions, deletions, replacements, are numbered sequentially as you do them.) You can look up the number of the actions on the leaves of the undo tree via :undolist. This will let you jump between branches easily. You can then use u and Ctrl-R to move up and down that branch.

There are some good examples in the Vim help. The best way to figure out how this works is to play with it a bit.

I'm a bit late to the party,
but I figured I'd mention that I wrote an undo tree visualization plugin for Vim :
https://github.com/sjl/gundo.vim

Personally I found that graphing the tree like this was the only way I could make sense of it.