http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2005-04/msg00151.html
First, use OpenOffice.org Writer (for example) to generate a single-page PDF file that has the needed header/footer/watermark.
Second, use pdftk's background option. Quoting from the man page of pdftk:
pdftk in.pdf background back.pdf output out.pdf
the back.pdf is the file you created that has the needed header/footer/watermark. The in.pdf is the file you need to apply header/footer/watermark to. The result, of course, is saved into out.pdf.
You can also use the dual option stamp instead of background. This will overlay the back.pdf on top of every page of in.pdf.