Finally (2013!), annotating PDFs has become a native & easy thing to do in Linux. I installed Xournal with ‘apt-get install xournal’ and got stuck straight in. You can save the file as a (tiny) native .xou file format, and also export back to PDF (views fine in evince). No more finding a Windows machine to use Adobe Pro!
Stumbled upon via: http://brutusfacticus.wordpress.com/2013/03/04/pdf-highlighting-annotations-in-gnulinux-okular/