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.