Clearing History doesn't delete the history of sites visited with Safari. They are listed in ~/Library/Safari/History.plist file. One can view the sites visited in that file with OmniOutliner.
As for the search engine, click on the magnifying glass icon in Safari's search engine for the list of recent searches.
Edited by Buddyme2, 08 April 2010 - 05:25 AM.