Some ways to get clients:
1. Optimize your own website for industry related terms + your locality. Such as "SEO in Seattle"
2. Try online SEO marketplaces, such as GAF, Elance etc
3. Approach local web dev and designing houses that don't offer SEO services and make a deal to offer your services to their clients looking for SEO solutions and in return you pay them a certain % as referral bonus for recommending you as an SEO provider.
4. Offer great results to your existing clients and get testimonials from them to display on your website.
5. Participate in some large online SEO communities and contribute generously to help people seeking advice...you will get some good contacts from these places.
But nothing works best as WOM promotion, if you provide extraordinary results to your clients in terms of ranks, traffic and sales, they will talk about you to their associates, friends and colleagues and this will lead you to more SEO contracts.