Go and visit them. If you look at any of the bigger marketplaces or on demand apps in the market at the moment, most of them started by getting a few people signed up on the demand side. They did that by physically going out and talking to them, demoing the product, explaining why it works, what the benefits are and frequently physically taking them through the signup process. If you do a bit of relationship building with your supply side providers, you'll be amazed at the results. Assuming your idea is good, has demand and is easy to use, those service providers you talk to will be some of your biggest advocates. They'll talk to their colleagues and friends in the industry and hopefully tell your story on your behalf. You effectively want to create advocates on the supply side. Also, that personal relationship will allow you to get invaluable feedback that you frequently wouldn't have thought of.
I've just invested in a marketplace in the Middle East. Our product is almost ready for beta. We've been out talking to the people who will be our service providers for the last month (and we probably won't launch for another month), showing them screenshots, talking to them about what they need and what would help them and generally gauging interesting and getting numbers signed up. We've had some amazing feedback and have introduced a few small features into the apps on the basis of the most common pieces of feedback.
Go out and talk to people. Hit the bricks. I guarantee you the results will be immeasurably better than direct mail, adwords or anything else in the early stages.