I just completed a random trip through the internet; choosing public library websites to see how they convey "search" on their pages. Only one of 10 did the same thing we did (yea Orlando!) while others had a variety of options:
~offering no search box on the home page but links to the catalog or to "search the site"(Salt Lake City or New Orleans)
~simple "search the catalog" box (San Francisco Public) to multi-optioned "search the catalog" box (Phoenix Public)
~"how do i find" box with many options to choose from (Boston Public)
~federated-like searches such as New York Public where the search box returns results from its website and their 3 catalogs, same with Hennepin
Some have a "link to site map" feature - do you use this? I've searched for this only in desperation when I haven't found what i'm looking for on the site using their navigation. Do you ever "search the site" on arapahoelibraries.org?