Like so many interfaces, web sites really still have to be hit-me-over-the-head stupid simple to allow users to be as quick and successful as possible.
Check out the link below where a fellow Tar Heel did some heat-map experimentation with users finding and using the search on WRAL.com. Simple and bright win out in the end. While it pains web designers and some developers, tried and true ways should continue to be well… tried and true.