MarZ has a good how to get hired thread started at SEW. He's noted that many guides exist for how to select the right SEO, what questions to ask, etc. but little focus is on how SEO firms and individuals can get clients to sign up with them. I've added some suggestions of my own;

1. Don't chase the client, let them come to you - trying to sell someone on SEO who doesn't recognize its value is tough, and there's plenty of companies out there who know they need to be competing in the SERPs - go to them first.
   -
2. Use honesty to sell them - Be forward about every step you're going to take, explain the basics of kw research, targeting, info architecture, design, usability, tracking and conversions and make them so comfortable with your skill and overwhelmed by information that they're ready to leave it all up to you. No one can do a good job when the client is watching over their shoulder.