Если заголовки колонок поместить в <THEAD>, то Firefox, например, автоматически будет их печатать на каждой странице.
К сожалению, ни IE, ни Opera пока так не умеют. (или я просто не нашел, как их этому научить?)
Но есть и обходное решение.
HTML с таблицей запросто открывается в Excel, а там уже есть File > Page Setup > Sheet > Rows to repeat at top