Clearing your browsing history from Chrome is not the same as clearing your search history from Google Search. To do the latter, you have to go into Google settings (either "settings" at the bottom of the google.com page while you are logged in, or the Google Settings App in your app drawer). Using the app, you'd go to search & now, accounts & privacy, and pick Manage Web History. There is also an option to turn off saving your search history.