I'm not sure that's true any more. Yellow pages is dying out in favour of the interweb. I tried yellow pages a couple of years ago and had only one person come from it despite it being a quarter page ad. Almost all my new students now come from seeing my website. Having been around for a while it is ranking well on the search engines and so is easy to find and full of useful content.
Get a website and advertise that all over the web. You don't need to spend a lot - there are loads of free directories etc.