Just got to History->"Clear History". And, also, use Safari->"Private Browsing" (aka Porn Mode) to cover your tracks.
Note that any URLs in your bookmarks (or those that come with Safari) will continue to show up as you type in a URL, even if you have an empty History.