Internet Marketing Ninjas put together this look at the history of search. They give a timeline of each and every search engine from start to where they are now. The icons denote whether the site was retired, purchased or redirected.
Seeing some on this list reminded me back to the old days before Google, I think I used Magellan quite a bit before I found Alta Vista. They also broke down what gets searched for the most by website.