Há um recurso para adicionar anotações usando o padrão gnome evince, mas a ferramenta não tem o recurso ativado no Ubuntu 10.10, então você pode escolher entre:
pdfedit - Ferramenta dedicada para edição de arquivos pdf.
flpsed - Útil, mas não tão polido.
inkscape - Importando o pdf, adicionando suas notas visíveis e exportando de volta para o pdf, a desvantagem é que elas não são notas de pdf reais.