If you are looking to do a search via the android app there are several ways to.
First one is through the main "Deals" screen and then clicking on the magnifying glass in the upper right
After you click on the magnifying glass you will be able to search through the entire organisation - workflows, deals and contacts can be looked up like this.
If you are looking to search through tasks then the procedure is similar except you need to click on "Tasks" icon at the bottom and you can search through the available tasks.
If you are looking to search through contacts once again - click on the "Contacts" icon
and then on the magnifying glass
and then type in the first or the last name of the contact you are searching for