The present invention relates to embedding a document with multiple watermark components at different printing stages. A document is preprinted to include a first digital watermark component. The document is then reprinted, perhaps with a lower quality printer, to include a second digital watermark component. In some cases the first component provides an orientation signal that is useful when trying to detect the second component. In other cases the first and second components are related or otherwise used to determine the authenticity of the document. In still other cases, the first and second watermark components carry information useful in determining the type of document, watermark-embedding hints and/or personal or serialized data.