First and fore most you must distinquish between PR & Marketing.
Sales & Marketing go hand and hand. PR & brand awareness go hand in hand.
Taken simply we're looking for 'sales' (ie new clients). To achieve this we (bring our goods to) market (the place our customers are). Our customers (not clients yet I'll differentiate later) are businesses looking to have their accounts & returns taken are of.
So take your 'services' to where they are. That's marketing.....
Now the method to reach customers differs according to the segment which we wish to serve.
Using the internet; online directories etc are excellent forms of exposure to customers surfing as webmaster rightly points out. Without a doubt the most inexpensive way to receive introductions. However this is not where most businesses start or end their search for quality business introductions. It also takes time to develop but in todays world you must incorporate this as part of your overall marketing strategy.
The most successful is of course personal referrals. This is takes time to develop so the simplest way (I didn't say easy) is to pigback another service provider. We all have to 'sell' ourselves our businesses... you cannot survive without these skills...no matter how good an accountant you are... Sales comes first...thats what sbeing in business means.
TIP
Find an affinity group, introduce yourself, your business; explain your need for new clients and how you are unique.
I'll give you one example. If you can't get referrals from this you need 'Business Advice'.
Visit the nearest Business or Enterprise centre (use Yellow pages or Yell), show them your services. Offer to give free 'bookkeeping' talks at their nightclasses/ daygroups of potentially new Business Startups.
Where I live 4 out 5 of these individuals start into business within 6 months........
Sorry about grammar etc...