This document covers how to squeeze a PDF onto half the paper, by putting two pages of the original document onto one page of the output document. You can save more paper by printing double-sided, if your printer supports it.
I did this on Ubuntu Hoary. You will need the following to use this howto:
Here are the steps to convert our hypothetical mydoc.pdf file into a new half-page-count PDF and print it intelligibly with xpdf.
pdfnup --orient landscape --nup 2x1 --outfile mydoc_new.pdf --paper a4paper mydoc.pdf
lpr -o sides=two-sided-short-edge