I managed to figure out how to support native browser undo in a simple way. Ironically once I had done it I found out that most browsers don't even support their own native undo very well...but at least you can keep up with them. It's tested on Webkit (works great), Firefox (works great, but Undo menus don't enable ever), iPhone (shake to undo/redo), and Android (how do you ask the page to undo?)
I made a single page that shows how to do it, and designed it in a way that you can easily copy it into your pages. It's licensed as non-commercial freeware.