Search not working in Preview.app
I selected the "Table of Contents" in "View Menu" and searched again. It is working. Check the screenshot:



Anyway, make sure that your PDF contains texts and not the image of some texts.