I am thinking of supporting Quick Search Box in my Android app. I would take what the user has typed and run a query on a remote server via web services. Is this pattern efficient enough or is it expected that any data I am querying should be displayed from locally accessible data?
Well, provided the server you are using is fast enough, no reason not to do that. The quick search box explicitly supports merging of results from local data and the web (see line #1 of http://developer.android.com/resources/articles/qsb.html).
As long as the fail is graceful (for situations where there is no network connectivity) you should be fine.
EDIT: odd, they got rid of it in the recent redesign. There is a mirror at http://jayxie.com/mirrors/android-sdk/resources/articles/qsb.html, and you can read up on the search suggestions at http://developer.android.com/guide/topics/search/adding-custom-suggestions.html.