One of the single most useful packages when it comes to PDFs in Linux is pdfjam.
From the website:
The installation is easy as always:
apt-get install pdfjam
PDF is not exactly the most easily editable format out there, but these tools can save you lots of time and trouble. Just recently I needed to merge two PDFs into one (and I didn't have any source format of the files). A simple
pdfjoin foo1.pdf foo2.pdf --outfile bar.pdf does the job in a few seconds.
Equally useful when you need to print huge documents is
pdfnup --nup 2x2 foo.pdf, which sticks four PDF pages into one (thus drastically reducing the amount of pages you have to print)...
Update 2006-09-20: As was noted by several people, pdftk is very cool, too. It can do some other things such as split PDFs, encrypt/decrypt them, manipulate metadata and more...