EDIT 18. 12. 2010: I posted a better solution with FormulatePro

EDIT 17. 12. 2010: Before commenting – As said at the end, this procedure is quick and dirty adding an image to an existing PDF AND the end result is an image converted to PDF which has lost all PDF advantages and benefits! Such documents are fine for e.g. quick printing. For better results try the command line tool pdftk (options stamp or multistamp), Formulate Pro,  or Acrobat Pro.

I wanted to add a logo of a university (a PNG image) on a document I had in PDF. It is fairly simple to do this in Preview:

Document.PDF

1. Convert the PDF to an image with File -> Save As -> … Choose PNG as a Format and change Resolution as desired

Logo.PNG

2. Switch to the logo image and select the whole image with Edit -> Select All (Command+A) (or select just a part of it with a mouse if you wish)

3. Copy the selection Edit -> Copy (Command+C)

Document.PNG

4. Back on the document (which is now the PNG image!) paste the selection with Edit -> Paste (Command+V) and resize it as you wish

5. Save it as PDF with File -> Save As -> … Choose PDF as Format (rename it if the original PDF needs to be preserved!!!!).

There are some drawbacks in this procedure (a PDF made from an image is not searchable), but that’s another story :).