Google Analytics has a report that shows conversion rate of people who use your site search box, and the percentage of site visitors that use it. If you notice that the conversion rate is really high (relative to site average) and utilization is really low then you could do what thefresh20.com does. They have a search graphic element anchored to the right hand side of browser …
… that scrolls with you as you scroll the page (looks like its floating). On click a search box springs open—
Nice design implementation that minimizes screen real-estate usage while making it super easy for shoppers to run a search query.