The elisp info documentation (section 32.9 in emacs 24) tells you what kind of information you have to keep track of and how to do so.
I've also noticed that you very often get "undo" for free if your command make changes in "normal" ways. I assume that "the unit to undo" is a single M-x CMD, but I've never researched this.
,Doug