Many applications are capable of generating PostScript. Since PDF is actually a container format that relies on PostScript for the actual document image, generating PDFs from PostScript documents is trivial. The GhostScript package processes both formats and comes with a script called ps2pdf(1) (Debian package: gs-common) which does exactly what its name suggests. 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.
See the notes below for hints about using ps2pdf/ghostscript.
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.
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. It also has Export to PDF... which allows you to save optimised for Size, Print, or Press.
Hint: OpenOffice will embed TrueType fonts into the PDF file it creates. You may get better results if you use fonts with the same name as the "core" fonts built into the PDF file format. For example, use "Times" instead of "Times New Roman" for your serif font, "Helvetica" as your sans-serif font, and "Courier" as your monotype font. If you do this, then no font information needs to be embedded in the PDF (which some viewers might have problems with), and the PDF file is smaller as a result.
gs -dBATCH -dNOPAUSE -sDEVICE=pdfwrite \ -sOutputFile=/tmp/merged.pdf file1.ps file2.pdf file3.pdf ...
The windows version of OpenOffice will work, as discussed above.
The SambaPDFPrinter described above can almost certainly be shared via samba and printed to from Windows Applications, something similar can probably be done for the CUPS version mentioned above as well. If I ever get around to setting this up I'll wiki the results.
PDF-creator is a special PDF printer driver for Windows, based on GhostScript. (Released under GPL). This method has an advantage over the other Free methods in that it allows you to set access/print/copy permissions on the generated PDF. One disadvantage is that it must be installed by an Administrator. (In contrast, you can install and run OpenOffice as a normal windows user.)
If you don't have any PDF software installed (either Adobe or other), and just want to convert a Word document to PDF, there's an easy-to-use service at http://www.fastpdf.com. You upload your document, and enter your email address, and the service sends you a note when the conversion is done. (You then pick up the conversion from the website.) The service is free for short documents, and relatively inexpensive for longer docs ('much' cheaper than purchasing Adobe's software!). Note: this is a somewhat shameless plug (since I built the thing), but many people do find it convenient.
As with any PDF conversion service, Fast PDF can get confused by unusual fonts found in Word docs. But if you embed the fonts you use in your document prior to submitting it to the service, the service works very well.
In practice, the service adds a Converted at Fast PDF watermark in the margins of conversions done for free (but not those paid for).
This can be a problem when the document contains Macrons and other characters not in all the standard character sets. The following technique appears to work at least in some cases where you have a PostScript printer visible and Adobe PDFWriter installed.
The PDF file will almost certainly look dreadful because all the fonts that make things look nice on the screen got thrown away in the Print to file step. It should print nicely however.
You can use the MS Imagesetter Printer that is created by the Commercial Printer option when installing Publisher. This creates a pair of pseudo-printers on a Windows box, which can be used to Print to file if the app doesn't support such. The printers are called MS Publisher Colour Printer and MS Publisher Imagesetter and both are capable of colour. The Imagesetter one seems to work better.
The following have been tested under OSX 10.3 (Panther) only; someone else might want to confirm them on earlier versions.