If you take care of the customer, the business will take care of itself. I have operated as a sole trader for a while and never had to advertise beyond my existing clients - the work comes in.

As for starting to find new customers; business cards work well and even stick some on the community notice boards or do some flyers. Ask some popular places if you can leave a stack of business cards on their counter (competing companies wont let you do this of course, but different industries, like a pet shop or local coffee shop).