I work for an IYP and can talk generally about our experiences. At the moment 70% use the big search box on the home page. They can't miss it. 30% come via search engines. The split might be 60/40 or 50/50 since some users type "yellow pages" into Google and arrive at the home page search box. :)
We don't present a prominent Browse by Categories anymore. When we did, less than 1% used it. But this depends on how you present it. Other IYPs list some major localities and major headings on their home page. We don't.
We have a discreet Browse by State, where they can browse headings by locality, then ultimately get a list of business names which show the A page by default. However, they choose the desired locality first and often a small suburb might not have many listings for a given heading, e.g. Abattoirs.
Nonetheless, as the search box usually brings the user into range, they can further refine and sort in many ways.