Actually, very simple.

aptitude install seahorse seahorse-plugins
killall nautilus

Run seahorse and generate your PGP key and next time when you run nautilus, you’ll have a new option when pressed right click on file or folder – Encrypt…