Do they approach lots of sites offering their service The reason i ask is i would get about 90% of people who own a website for their business really dont understand anything about "keyword rankings" or "link building" so how do they get work? Im not sure people who use a site to promote their business would search for seo company's or even know what to search for if they dont know the term "seo"
Of course you need to advertise your service or business.... and in order to have customer, you must prove that your site also has a high rank... and you must build a good portfolio of testimonials.
Yes they won't search for one ... but they will ask in forums, call the company that made the website and ask why it's not working and they will direct them to a seo company or tell them for what to search.
I think the most successful SEO's have shown that their own website or websites they own rank well in search engines then from there get as much local business as they can because these people have less knowledge about the SEO industry and what it could do for them than someone searching DP. Also many people now are thinking negatively about SEO because it is not an industry where you can get results overnight and there are many people who do not actually know what they are doing who have SEO companies.