Atualização (graças a @fifaltra por me indicar, veja os comentários)
O novo local de anotação é:
~/.local/share/okular
eles foram armazenados anteriormente por padrão em arquivos xml localizados em
~/.kde/share/apps/okular/docdata
ou melhor
$(kde4-config --localprefix)/share/apps/okular/docdata/
independentemente do fato de você estar usando o gnome ou não.