Apparently everyone uses his own proprietary format to store and export annotations. The FDF format (or better its XML variant XFDF) is or was used by Acrobat to store form values and annotations, but third-party implementations focus on the forms-part of FDF instead of the annotations-part.
iText classes (no full FDF/XFDF implementation)
The commercial software "Adobe® Digital Editions" explicitly supports external annotations. The FAQ says "Digital Editions supports bookmarks, highlights, and text notes via its bookmarks panel. These annotations are stored in an open XML format separately from publications to enable seamless annotation across PDF- and EPUB-based publications. They will set the stage for future social networking features (such as sharing annotations within a community of readers)."
Okular has its own annotation exchange format, similar to PDF annotation (comparision is needed)
Xournal is open source and allows some annotation, but its PDF reading ability is very limited. It also uses its own format to store annotations
Mendeley supports annotations, which can be synced independent from the PDF files they refer to, and exported together with PDFs. There is no documentation of the API and format they use to exchange annotations.
Evernote is worth a view. But proprietary and no Linux client.
iAnnotate seems to be popular on the iPad - can it export and import annotations? In which format?
There is a good article by Scott McLeod with screenshots about his use of iAnnotate and Evernote to take notes (June 15, 2010).
Several tools allow for annotating images (Flickr, Wikimedia Commons, Omeka/Neatline...) but no general exchange format exists (?). At least the simple subset of (sets of) rectangular annotations should be easy to define and implement.
The simplest form and most common case consists of just a time or time span.