Select Add Headers and Footers from the Document menu.
Select either Header or Footer according to preference. Make the selections for the first one (e.g. even pages), then select Even Pages Only, in Alternation under Page Options. Alter the Margins if necessary. Click OK. Then go through the process again with the odd pages, removing the one you put there earlier from the box.
I just tried it and it worked.
tgreer This is with Acrobat 6. Adding headers and footers (including page numbers) is one of the new features of 6 (jskang specifically asked for how to do this in Acrobat 6 - you can't do it in any of the earlier ones, except using form fields and javascript, I think).