Wish there was a quicker way to cover your tracks and protect your privacy from prying eyes? Then you need HistoryEraser.
It's a free app in Android Market that does exactly what its name implies: erases your history. Sure, you can already erase your call log history in the phone app and your web browsing history in the browser, but HistoryEraser lets you do that plus delete your search histories in Android Market and Google Maps all from one place. There are also options to erase YouTube searches and Search shortcuts, but they're labeled with "Assist," which means they take you to the respective settings menus to manually clear the search histories yourself.
The Market, Maps, and YouTube options are supposedly still in beta, but they work perfectly on my EVO. I don't know if the developer has any plans to do more with the "Assist" options, but the app is still useful as is.