Originally Posted by HarryT

Go to the home page and search for a string of random letters (so you don't get any real matches). On the search results page, if "Text in Books" is not greyed out, tap it and it'll say "23 books not yet indexed" (or whatever the number actually is). Tap that and it'll show you what the books are that haven't yet been indexed.

When you do add books, leave the Kindle connected to a wall charger until they've finished indexing. Indexing happens a lot more quickly when the Kindle is connected to a charger.