Stationery, or other printable media, is encoded with a digital watermark. The watermark is not conspicuous to a human observer of the media, yet conveys plural bits of auxiliary information when optically scanned and digitally processed. The watermark can be formed by ink-jet printing, or otherwise. The encoded information can be used for various purposes, including authenticating the document as an original, linking to associated on-line resources, and distinguishing seemingly-identical versions of the same document (document serialization).