E' certamente nelle repositories di Debian.
Su Ubuntu non so, ma sul suo sito (Recoll ) ci sono i pacchetti per Ubuntu (e anche le istruzioni su come usarlo).