PDFTK (get from Synaptic)
* Apply a Background Watermark or a Foreground Stamp
pdftk [input filename="filename" pdf="pdf" ] stamp [stamp filename="filename" pdf="pdf"] output [output filename="filename"]
I made a transparent background GIF with GIMP, converted it to pdf, with Mogrify, and applied it to the pdf.
Application of a different size watermark image than the original pdf page happens with scaling the watermark image to fit the height and with keeping the watermark's size ratio, and fitting it in the center of the original page.