Select each sheet (tab) while holding the Ctrl key. Once you have your
array of worksheets selected, goto File | Page Setup | Headers and Footers
... you know how to do it. From there, after you Ok out of that, just
right-click any selected sheet and click Ungroup Sheets.
You can group the sheets (click on the first tab and ctrl-click on subsequent
tabs). Then File|page setup and change the headers/footers.
Remember to ungroup the sheets (just rightclick on any of the grouped sheets and
select ungroup sheets) or you may damage your workbook. Almost anything you do
to a one sheet (of a group) is done to the rest of the sheets in that group.