Lifehacker and the EFF have put together guides for removing your search history from Youtube and Google Web Search, respectively.
However, when I was considering this, I didn't like the idea of just deleting the past 7 years of history, losing all that info. Google's Data Liberation Front has an explanation of how to download this history, but it only includes the past 100 entries. So I searched a little deeper, and found this.
Script to download Google Web History
You basically install this as a bookmark, and then go to http://google.com/history, click the bookmarklet, and let it export all of your history as a CSV file. Which is exactly what I wanted. After storing this file, I then felt free to delete all my past history per the above instructions.
This won't help with Youtube history, but for me, that wasn't nearly as much information.