To enable History Sync, navigate to the "Sync" pane of the Xmarks Settings dialog (Tools → Xmarks Settings → Sync) and click the checkbox next to History:
Do the same thing on two or more computers running Xmarks for Firefox, and those computers will automatically and silently start exchanging history information. Easy!
If you're interested in understanding more deeply how it works and some of the design trade-offs we faced to make this happen, read on below the fold. And feel free to let us know how it works for you in the comments.