Answer: The Non-Linear History option goes back to the creation of the History palette in Version 5.
By now, most are used to the History palette. It's like a list of available undos. Don't like how things are going? Open up the History palette and go back to an earlier point in your work. This is the default way of working with the History palette - a linear way of working.
Non-Linear History works a bit different. Select a previous state or snapshot and you'll revert to that point. The next task that you perform will build from that point. Just like Linear mode, the new states will be added to the bottom of the list. With Non-Linear History, those intermediate states (the ones that you un-did) stay in the palette. They aren't removed or dimmed. They just stop contributing to the image.
The main advantage to Non-Linear mode is that you retain everything. Nothing is thrown away - every step is preserved even if you've reverted and moved on. This can save time later if you decide to go back to one of these "off-line" states to try something else. The disadvantage is the confusion caused by the fact that there is no clear way of looking at the palette and telling which states are "on-line" and which are "off-line."
My advice ... if you are using Non-Linear History - take a lot of snapshots and label them descriptively. If "save early-save often" is part of your mantra, then consider checking the box for "Automatically Create New Snapshot when Saving."
Thanks again for the great question. Keep them coming.