Есть два варианта: первый - вставить нужную линию в колонтитул, для этого вам нужно будет переопределить команды \@evenhead и \@oddhead для верхних колонтитулов или же \@evenfoot и \@oddfoot для нижних; второй - при помощи команды \everypage. В любом случае вам нужно будет вставить рисунок в \vbox to 0pt{\hbox to 0pt{рисунок}}, чтобы не нарушать разметку.
В общем, читайте Львовского, Балдина, Кнута.
-- Чт ноя 18, 2010 09:17:49 --
И да, у вас линия горизонтальная, лучше и правда ее сделать командой \hline.
Спасибо