Open Google Now (like tap in the search box), Menu button, Settings, Accounts and Privacy, theres on/off switches for history, delete items, etc. You can also go to the last item (search engine storage) at the bottom, and scroll down and choose "Clear now".