AboutHippocampus is a chrome (eg. priveledged) sidebar that searchs bookmarks and history. While the Mozilla sidebar offers bookmark search it doesn't do history search.
In general, the history sidebar is lacking. A future iteration of Hippocampus will provide recently visited pages for quick access to your recent surf trail.
Hippocampus also allows you to do Google queries if you have a Google API license key, via Alex Hodel's GoogleAPI implementation. Specify your key by editing the file .../mozilla/chrome/hippocampus/prefs.js.
Here's what it looks like:
While untested on anything but Mozilla version 1.3 at this point, Hippocampus should work all the way back to Mozilla 1.0 on Windows, Mac, Linux, etc.
Install the 0.6.0 XPI
Once installed, you'll need to restart Mozilla and enter the following into the urlbar: chrome://hippocampus/content/install.html
Feedback & Planned Features
Check out the notes page for planned features and to leave your suggestions/comments.
0.8.4 Ctrl-click to open in a new tab
0.8.3 Adds stop button. Slightly faster. 0.8.3 XPI
0.8.2 First stable release. 0.8.2 XPI