PostScript and PDF are quite similar in some respects, and it is easy to generate PDF from it. The GhostScript package is capable of understanding both formats, and it comes with a script called ps2pdf which does exactly what its name suggests. Many applications are capable of generating PostScript. Older versions of GhostScript (such as the widely used version 5.50) embed any non-core fonts as bitmap fonts, which AcrobatReader doesn't do a very good job of rendering. More recent versions of GhostScript (6.x or 7.x) do a much better job of embedding scalable fonts in the document.
You can set up a fake printer that will generate a PDF file. Most of these techniques are wrappers to ps2pdf. This means you can make a PDF file from any program that can print. See the SambaPDFPrinter and CUPSNotes pages.
You can use LaTeX (pdflatex(1) or LaTeXpdf are good places to look) to make good quality PDF files.
Version 1.0 of OpenOffice allows you to set up a special PDF printer. From the correct installation directory (such as /usr/lib/openoffice/program), run ./spadmin, select "New Printer" and then "Connect a PDF converter" and then OpenOffice will see its own special extra printer. Debian has a wrapper script called "oopadmin" that you can run from any directory.
Version 1.1 of OpenOffice does PDF "natively" - it is merely another filetype you can save as, rather than setting up fake printers.
3 pages link to CreatingPDFs: