Once in a while I am looking around if there is finally a way to properly annotate PDF in Linux. The answer was no until a couple of months ago. But I think it is still little known.
Even in this post, whose comments made me have a close look again, did see the option of embedding annotations into PDF. The comments, however, point to Okular which is a very good reader since quite some time, and a more or less recent version of poppler the PDF library.
The way to go is to make annotations with Okular (use the review tool (F6)) and then save the PDF with “save as”. Now the annotations are embedded into the pdf file. I tested the annotations with the Adobe Android reader and I can view them and alter them with it.
Unfortunately this information is hidden in the Okular handbook and not really updated on the Okular page. Anyway I hope the Okular team is thinking of making the process a bit less tiresome by providing an option to save a PDF straight away.
I tested it with Okular 0.17 and poppler 0.22, both packages of fedora 19.
 Just now as I wrote this article for the first time Okular produced a popup at the first annotation today, explaining what I wrote here. It might be appearing a bit randomly, though.