With the latest versions of Preview.app (since OS X v10.8, I believe) which save versions of files rather than the old standard Save dialogues, it took me a while to figure out how to Save As… and encrypt a PDF file with a password.

While clicking on the File menu, press the Option key, which causes the Duplicate menu item to become Save As… instead. Then you’ll see the familiar Save As.. sheet with the Encrypt checkbox. Enabling this allows you to set a password for the PDF file.

[crarko adds: I tested this, and it works as described. This may be common knowledge, but serves as another example of why it’s often helpful to explore the modifier keys in an application before getting too frustrated.]

Source: Mac OSX Hints