I have added a small search box at the top of the default theme. Now you can search from any page.

I've also removed the quick search block from the Home page since it's not really needed anymore. I will most likely embed a search form somewhere on each theme.