Se você se sentir confortável com a linha de comando, poderá usar o pdftk para fazer o trabalho.
Aqui estão os passos:
1) Generate a pdf with your header where you want it (bkg.pdf);
2) Use the following command to add the file from 1) as a watermark;
pdftk inputfile.pdf background bkg.pdf output outputfile.pdf
Você pode gerar o arquivo de cabeçalho com, por exemplo, LaTeX, ou com o Word ou outra ferramenta de processamento de texto, mesmo TextEdit.app.
Editar: Dependendo do conteúdo do seu PDF (por exemplo, um documento digitalizado), você pode preferir uma "marca d'água" em primeiro plano para cobrir as imagens; Nesse caso, você deve substituir 'background' por 'stamp' no comando acima.
Tenha em atenção que poderá necessitar de algumas iterações para se certificar de que as coisas estão alinhadas de forma adequada.
Opção alternativa: use o LaTeX para gerar o cabeçalho e inclua todas as páginas, mas é um pouco mais complicado.