Always a tricky subject to ask for advice with!
Ask at least 20 people where they would look to find services such as yours, don't push them into an answer though - that will give you an idea how people think, you can't answer this questiion yourself!
Focus on a small area at first and get your name out there, try and offer something for free - something that people will remember you for and talk about. Lots of small affordable adverts everywhere is better than one huge advert in one place.
Have thousands of leaflets printed and get the local children to deliver them for you - maybe go out early morning and find all the newspaper boys and girls and get them to add a leaflett to each delivery. Every spare minute you get, walk the streets and deliver those leaflets. Ask the local stores to display them on their counters, offer them a free hour when and if they need you!
Recommendation is clearly the best, offer a free hour of your time for anyone who sends you 5 new clients.
Follow this for about 3 months, make sure you ask every caller where they found your number and record it - after 3 months you'll know which advertising works best, then invest more money into that!
Leaflets definately work for me, I usually get one job from every 50 delivered also a must: is a company website!!!
I never have had business cards as I think they are a waste of money, just give them a few leaflets.
One other thing is stickers, get some small good quality stickers made up with company name, phone number and your name - make sure to stick one on every computer you see. People lose leaflets and throw them away - that sticker will be there for years!!
Good luck!