Wow, you could write war and peace on how to get new clients, and more specifically how to deter them!! The obvious choices are leaflets, shop posters, local press advertisiing, incentive offers eg free gift at 1st appointment, good professional shop front displays and signs, but to me the biggie which shouldnt be under estimated is word of mouth. Do your absolute best for each and every client, be friendly and helpful, show concern and interest for the ongoing health of their nails, and those friends will be likely to a) stay loyal to you and b) tell their friends about you.
My local area has a free publication, its an A5 glossy mag with articles about the local area, and adverts for local businesses and its really cheap to advertise. I just paid £90 for a half page full colour ad, artwork included, and that get delivered to 10,000 homes in my local area. Its published in April so I'll let you know what the response is like.