Recently a new version of Foxit Reader is released for Linux. It has the highlighting and annotating support. It has more annotation options than Okular, including inline notes with transparent background, drawing of various shapes etc.
How to install Foxit Reader in Ubuntu is explained in this AskUbuntu answer:
Install FoxitReader
Actually, none of these solutions work half as well as anything on Windows or Mac OS.
Mendeley only supports yellow highlighting and importing pdfs into Inkscape or OpenOffice is pretty inconvenient if you want to read a paper and simply make some annotations.
Fortunately, there are some free pdf viewers for Windows that work flawlessly with wine (If you find wine too complicated, use PlayOnLinux - a great front end for wine configuration). One of the best of those viewers is the PDF-XChange Viewer by Tracker Software. There is a free version that comes with a ton of annotation features, session saving etc. Grab it here:
The evince package which is built-in in Ubuntu and is called Document Viewer can add annotations to PDFs.
Evince 3.18.2 from the Ubuntu 16.04 default repositories has support for highlight annotations and moving annotation icons to a different position on the page.
If you do not have a visible side pane on the left side of the opened document's window, click View -> Side Pane or press F9 to make the side pane visible. At the top of this side pane, there is a dropdown menu with options like Thumbnails, Index and Annotations (some of which may be dimmed for some documents).
To create an annotation
Select Annotations from the dropdown menu. You should now see List and Add tabs under the dropdown menu.
In Ubuntu 16.04 and later, click the toolbar icon that looks like a notepad. A new toolbar will appear under the toolbar with two icons for adding text annotations and adding highlight annotations.
Select the Add tab.
Click on the icon to add an annotation.
In Ubuntu 16.04 and later, the icon for adding a text annotation looks like piece of paper with a + in the upper right corner (marked by a diagonal yellow arrow in the below screenshot), and the icon for adding a highlight annotation looks like a piece of paper with three black blocks on it.
Click on the spot in the document window you would like to add the annotation to, preferably a blank spot where the annotation will not cover anything else in the document. Your annotation window will open.
Type your text into the annotation window. You can resize the note by clicking and holding the left mouse button on one of the bottom corners of the note, and moving it around.
Close the note by clicking on the x in the top corner of the note. You might need to hover over the x with the mouse to make it visible.
When you want to go an annotation click on the icon for it. If you can't see the annotation icons, then unfold the little black arrows to the left of the page numbers in the side pane to show them. The text annotation icon looks like a piece of paper with a pencil over it in Ubuntu 14.04 and it looks like a pencil in Ubuntu 16.04. The highlight annotation icon looks like a piece of paper in Ubuntu 16.04.
When you close the document you will be asked if you want to save the changes you made to it.
To create a highlight
The evince snap package makes the highlight text feature available to all currently supported versions of Ubuntu, otherwise the evince apt package in 18.04 and later also has the highlight text feature.
Click the pencil icon in the upper left corner. In some versions of Evince there is a small notebook icon instead of a pencil icon in the upper left corner.
Click the Highlight text button in the upper left corner.
Select some text with the mouse and it will be highlighted.
When you close the document you will be asked if you want to save the changes you made to it.
The highlight feature of evince can also be obtained in Ubuntu 16.04 by installing the evince snap package:
Having used multiple pdf viewers editors, and after 6 years (!) of asking this question, I settled in two different tools for different purposes:
Mendeley Desktop is an excellent reference managers and it works flawlessly in most Ubuntu versions. It is ideal for papers and academic writing and supports notes and highlights synchronization.
Evince (or Document Viewer), the default pdf viewer as of Ubuntu 18.04 also supports highlighting and annotations. To show the annotations menu bar, you must click on the red circle (see below). The annotation options appear and you can annotate or highlight as seen in the blue circle in the image below.
It just installs and works flawlessly under Wine. (Source)
The only issue is that sometimes when you scroll fast it shows some white spaces over the text, that clear when you click or select a line in the document.
There is an option in the Edit menu under Preferences\Performance\Threads Usage:
"Use synchronous mode of page rendering"
which prevents those white spaces in mine.
Okular supports PDF annotations.
To save the highlighting/annotations directly in the PDF document, choose File > Save as... and create a new PDF which will contain your edits.
How to edit in Okular
You can choose Tools > Reviews to get other options like adding
Edit: Inkscape supports PDF editing (one page at a time) and most people seem not to be aware of this so I'm adding it to the answer.
Recently a new version of Foxit Reader is released for Linux. It has the highlighting and annotating support. It has more annotation options than Okular, including inline notes with transparent background, drawing of various shapes etc.
How to install Foxit Reader in Ubuntu is explained in this AskUbuntu answer: Install FoxitReader
Actually, none of these solutions work half as well as anything on Windows or Mac OS. Mendeley only supports yellow highlighting and importing pdfs into Inkscape or OpenOffice is pretty inconvenient if you want to read a paper and simply make some annotations.
Fortunately, there are some free pdf viewers for Windows that work flawlessly with wine (If you find wine too complicated, use PlayOnLinux - a great front end for wine configuration). One of the best of those viewers is the PDF-XChange Viewer by Tracker Software. There is a free version that comes with a ton of annotation features, session saving etc. Grab it here:
http://www.tracker-software.com/product/downloads
And check out this screenshot:
I really wish there was a working open source Linux alternative (xournal is good but too limited). But for the time being, I am happy with using wine.
xournal is also some software which you use for this task.
Future version of Evince will support PDF annotation and highlight. Here you can see a video of the first partial implementation, made by Carlos Garcia Campos
If you want to try I think you need to have at least evince 2.32 and recompile yourself latest version of Poppler cloning from the git repository:
Here the launchpad bug of this missing feature from evince (poppler packaged for Maverick isn't enough updated).
21 april 2011 - Update Evince in Natty now support by default annotations (not highlighting). Evince in Natty is 2.32, poppler is 0.16.4.
08 March 2017 Update Evince in Ubuntu 16.04 supports highlighting.
The evince package which is built-in in Ubuntu and is called Document Viewer can add annotations to PDFs.
Evince 3.18.2 from the Ubuntu 16.04 default repositories has support for highlight annotations and moving annotation icons to a different position on the page.
If you do not have a visible side pane on the left side of the opened document's window, click View -> Side Pane or press F9 to make the side pane visible. At the top of this side pane, there is a dropdown menu with options like Thumbnails, Index and Annotations (some of which may be dimmed for some documents).
To create an annotation
Select Annotations from the dropdown menu. You should now see List and Add tabs under the dropdown menu.
In Ubuntu 16.04 and later, click the toolbar icon that looks like a notepad. A new toolbar will appear under the toolbar with two icons for adding text annotations and adding highlight annotations.
Select the Add tab.
Click on the icon to add an annotation.
In Ubuntu 16.04 and later, the icon for adding a text annotation looks like piece of paper with a + in the upper right corner (marked by a diagonal yellow arrow in the below screenshot), and the icon for adding a highlight annotation looks like a piece of paper with three black blocks on it.
Click on the spot in the document window you would like to add the annotation to, preferably a blank spot where the annotation will not cover anything else in the document. Your annotation window will open.
Type your text into the annotation window. You can resize the note by clicking and holding the left mouse button on one of the bottom corners of the note, and moving it around.
Close the note by clicking on the x in the top corner of the note. You might need to hover over the x with the mouse to make it visible.
When you want to go an annotation click on the icon for it. If you can't see the annotation icons, then unfold the little black arrows to the left of the page numbers in the side pane to show them. The text annotation icon looks like a piece of paper with a pencil over it in Ubuntu 14.04 and it looks like a pencil in Ubuntu 16.04. The highlight annotation icon looks like a piece of paper in Ubuntu 16.04.
When you close the document you will be asked if you want to save the changes you made to it.
To create a highlight
The evince snap package makes the highlight text feature available to all currently supported versions of Ubuntu, otherwise the evince apt package in 18.04 and later also has the highlight text feature.
Click the pencil icon in the upper left corner. In some versions of Evince there is a small notebook icon instead of a pencil icon in the upper left corner.
Click the Highlight text button in the upper left corner.
Select some text with the mouse and it will be highlighted.
When you close the document you will be asked if you want to save the changes you made to it.
The highlight feature of evince can also be obtained in Ubuntu 16.04 by installing the evince snap package:
-------------- EDIT March 2018 --------------
Having used multiple pdf viewers editors, and after 6 years (!) of asking this question, I settled in two different tools for different purposes:
Mendeley Desktop is an excellent reference managers and it works flawlessly in most Ubuntu versions. It is ideal for papers and academic writing and supports notes and highlights synchronization.
Evince (or Document Viewer), the default pdf viewer as of Ubuntu 18.04 also supports highlighting and annotations. To show the annotations menu bar, you must click on the red circle (see below). The annotation options appear and you can annotate or highlight as seen in the blue circle in the image below.
--------------------------------------------------------
For me the best solution was PDF X-Change Viewer.
The only issue is that sometimes when you scroll fast it shows some white spaces over the text, that clear when you click or select a line in the document.
There is an option in the Edit menu under Preferences\Performance\Threads Usage: "Use synchronous mode of page rendering" which prevents those white spaces in mine.
There is a package called pdfedit that can do this.
The PDF viewer in Mendeley allows you to highlight and annotate PDFs. To save the modifications you need to
File > Export PDF with Annotations.However Mendeley is not open-source, and it forces you to use an account... But otherwise the functionality is excellent.
You can download from here.
Now you can actually export annotations to PDFs in Okular (this was not possible until recently): http://docs.kde.org/stable/en/kdegraphics/okular/annotations.html
It seems Okular has to be built with Poppler at least version 0.20. It works with Ubuntu 13.04.