Open the stock Browser, tap menu/Settings/Privacy & Security/Clear History.
Open Chrome, tap menu/Settings/Privacy, and tap the "Clear Browsing Data" at the upper right.
Neither of the above options actually clears your Google Search history. That's a little more involved, and requires you to access your Google account on your desktop. Let me know if you want more details.
Not all apps allow you to clear their respective search histories. You need to look at the individual settings menus for those apps. I'm not sure if clearing app caches using something like App Cache Cleaner would clear a search history.