Mashable had an article recently on a search engine that doesn't track users with cookies or by saving search histories. It's appropriately named Stealth and is kind of like a private version of Google. To find out how it works, check out the menu under "Learn More." There's also a brief bit on why using Incognito on Chrome isn't such a good idea. This new search engine is so stealthy that the URL isn't quite what you'd think; instead, it's usestealth.com.
The icons are easy to miss, but right under the search box are options for images, news, and videos along with the standard web search. I don't know how the results compare to Google, Yahoo, or Bing, but I suspect Stealth's database of crawled or cataloged websites isn't nearly as big. (Stealth says, "We do a good bit of our own crawling and also utilize many different API's (Google's Ajax API, Bing's search API, etc) as well," but that doesn't explain how many websites or images or whatever are in its database.)
The only thing that bothers me is the need to scroll slightly to the right. For new computers this may not be an issue, but they could have made their screen size dynamic to fit whatever monitor size a user has.
Try it out and leave your thoughts and impressions in the comments.