Funnily enough, I've had reports of this today too. I assumed that it was related to the version of Play Services on the device, as the search option was only added to the place picker in December 2015: https://developers.google.com/android/guides/releases#december_2015_-_v84.
However, having done some debugging, it looks to be phone related rather than Play Services related as I have two devices running the same version of Play Services (a Nexus tablet and a One Plus One) with the search option showing on the Tablet but not on the One Plus One. Equally, these are both running a later version of Play Services than an old KitKat device I have which shows the icon fine. Very odd.
Resolved: Ok, so my app had been compiled with Google Play Service 8.3.0. Having now updated the version of Google Play Services to 8.4.0, I've had confirmation from users that the search icon is now showing correctly.