Search implementation

We other humble developers on other humble platforms (in my case, Android) are working through some of the design decisions you have undoubtedly already made.

For instance, I was wondering if there was something we could learn from you concerning the implementation of search.

1. How did you implement it?
2. Do you have the ability to search through all books loaded locally on the device?
3. Are you using the search web service?
4. If you are, how do you deal with situations and locations where there is no internet access?