First of all, make sure that you have a "good" act. I really mean this. So many feel that they have an act worth doing and yet it can be just attrocious and once you work, you may never work again and it will haunt you for a very long time.
Then some business cards and some promotional materials will aid too. A brochure, business cards, etc. As you perform, build up letters of recommendation from the clients that you have worked for and keep them, any press you have gained all in a scrap book. They will come in hand later. You will eventually need a video too but if you are just starting out, you can get to that later.
Then you open the yellow pages and start to call all of the "entertainment bureaus" in the phone book, party planners, etc....any business that might use your services. let them know who you are, what services you do and most importantly, find out what their needs and requirements are. (It is far better to find out what your potential client's needs are than espousing what you can do for them and your talents).
You might also get a small ad in the yellow pages BUT just because you have an ad in the yellow pages does not mean that you can just sit by the phone waiting for it to ring either. You still need to make phone calls to prospective clients, arrange agreements for you to post flyers at toy stores about your magic show, call libraries, schools, etc. and try to sell shows there too. Booking shows is hard work and I haven't even hit the tip of the iceberg for you but hoepfully that will give you a start.
Paul Alberstat http://www.stores.ebay.ca/abstagecraft