In the past, I used to manually set up the tool chain for PDF production on Windows.
Basically, this requires the installation of Ghostscript and a PS printer driver that prints to a RedMon port. The trick is to configure the PS printer driver so that it embeds Type 42 fonts. And I also need to have pdftk to set the document security and then stuff…
Well, that was indeed the past. 
These days I get lazy and just use the free (as in beer) product PrimoPDF. So far, I find it does everything right, but I still manually remove the Ghostscript 8.50 that is bundled in its installer (remove the gs subdirectory) and let it use the most current version on my computer.
Combined with the ability to split and join PDFs using pdftk, that’s a pretty good basic setup for everyday PDF production at a low low cost of zero dollars. I am all thankful!
Update: Many of you reminded me that I should really mention PDFCreator in this post as well. I agree. Both of them are great!
20:47 on July 5th, 2006
Quite some time ago I installed (on windows XP) PDFCreater . I am not sure what are your needs, but this free software works quite well for me, mostly for keeping copies of “temporary” webpages like receipts and reservations.
21:30 on July 5th, 2006
Yes, PDFCreator is also a very good option that I neglected to mention. Thanks for pointing this out. (And I must add that PDFCreator is free as in open souce. By this alone it is “better” than PrimoPDF.)
6:38 on November 30th, 2007
PDFCreator doesn’t support Vista or VistaX64 however…