Word of mouth works surprisingly well. Get into small talk with anybody you can and work in that you do SEO to as many of them as you can. You'd be surprised who's looking for SEO. Get a good looking business card and hand it out each time you bring it up.
Rank in your region for the terms.. SEO, search engine optimization, marketing, etc. Advertise on CraigsList, get a phone number for your business, make a nice looking ad. (You can use images in CL posts, and HTML, so making your ad look good is easy.) There's probably some type of community board on your local news website, get on all of those.
If you live in a big city, then CL can keep you pretty well tied up. When I lived in LA, I couldn't advertise every day.. I could only advertise about 2 days a week or else I'd just be swamped with leads. One thing that I always did with SEO services in the LA area was posted in the barter section, you can convert a lot of those into paying customers by not being interested in their shit for trade.
Also, like said.. Mainly be honest with your clientele. Treat your clients like you'd expected to be treated and that's how you'll get good word of mouth and future projects. Not to mention, that's how you'll KEEP your clients, period.