How can I annotate PDFs so notes are compatible with Adobe Reader for Win/OSX?

Look for the package "xournal" in the software center or user apt-get to install it. With it you can annotate PDFs and export them as PDF again.

Besides Xournal (see m4lvin's reply), you could use PDF XChange Viewer. The free version allows for annoting PDFs, too; it runs without problems using wine.

Newer versions of Okular can save annotations directly to the PDF file.

By default, the annotations are saved in the local directory for each user. However, if you choose "File" -> "Save as..." you will be able to save your annotations in a new PDF file, so that they are visible by any other PDF viewer. (See http://okular.kde.org/faq.php#annotateandsendtofriend )