If you are working a restaurant I highly recommend this book. It is one of my favorites.
Close Up, The Real Secrets of Magic- David Stone.
With my experience thus far after 14 years of magic, getting into restaurants usually / sometimes takes you "filling" in for another magician who has recommended you. Perhaps a family emergency comes up or they are on vacation. This is where networking with other magicians is huge. You scratch their back, they scratch yours which is okay, as long as you aren't under cutting each other. This is also why I recommend joining your local IBM ring or club if there is one nearby.
Or...sometimes it takes knowing someone who is high up in management. I know that stinks, but it is reality.
Now, what can you do if you don't have a connection with other magicians, an agent, and you don't know the manager or owner of a restaurant? I would try offering your services for one free night for 1 hour when the owner is going to be there and they can see or hear about how well you have done.
Or...here is another plan that has actually worked for me as well. Go into the restaurant that you are hoping to get hired at with a group of your friends. Begin performing magic for your friends (standing up) at your table (but make sure you are out of the way of the restaurant staff and servers or you'll promptly be told to take a seat). 9 Times out of 10, the nearby tables will begin to take interest and begin watching and perhaps clapping. The people at your table should be clapping or reacting as well. This will draw attention to yourself and create some interest. Before long management will see or hear about you and you may be approached so have a business card ready and perhaps 1 or 2 nice effects to show them if they request.
You should have 3 sets of effects on you that all "instantly" reset so that you aren't fumbling around between tables trying to get props set. It doesn't happen nor will you have time. I believe Jamie Grant had a really good thread on restaurant sets. I'lll see if I can find it.
Let me know if you have other specific questions. I don't claim to know everything but am just sharing what has worked for me and what I've seen happen in my area.