How to index a pdf document?
Tracker can index your pdf documents. It is very fast and reliable.
If you don't use this great tool yet, you can configure it to only index your pdf documents: Alt+F2 then paste tracker-preferences go to "Locations" and choose the folder of your pdf.
I'm not sure any of the pdf readers support text indexing - probably because the indexing itself would be rather expensive and pdf files opened and closed 'ad-hoc'
However, I've done some testing and can see that okular - the default viewer from KDE - has much faster search than evince (the default viewer from Ubuntu). I.e. it takes maybe a second for okular to scan the whole 500-page document, while evince spends ~5 sec on the same task.
You can install it by typing
sudo apt-get install okular
(or just search for it in the Software Center)
if this is the first KDE program on your machine it would require installing quite a bit of dependencies, but it may be well worth it - I'm finding KDE programs generally more capable then their Gnome counterparts... Okular supports pdf annotations, for example, which is also useful sometimes.
Alternate PDF viewer
Overview
A very lightweight and fast alternative to Okular that doesn't come with any of its KDE dependencies is qpdfview. It's still in beta but I found it to be just as stable as its big counterparts. Search performance is fantastic and at least on par with Okular.
Installation
Qpdfview ist not yet available in the official repositories but can be easily installed from the developer's PPA by typing:
sudo add-apt-repository ppa:b-eltzner/qpdfview && apt-get update
sudo apt-get install qpdfview
PDF indexing
Overview
I wasn't able to find an alternative to Adobe Acrobat's indexing capabilities on Linux and it appears that's because embedded indexes still aren't part of open PDF standards.
However, there are a number of very powerful desktop search engines out there that are both faster and more efficient in PDF indexing than Adobe's proprietary tools. Tracker has been mentioned already but there are other apps out there as well. You can find a very thorough comparison here.