I'm a gallery represented photographer and I can tell you what I know. I can see two paths into a gallery, the first is when the gallery owner is already familiar with you work, the second is when they are not.
You are lucky if you fit into the first camp, I did. But it isn't all luck. I worked hard to get noticed, I was just lucky in that I got noticed quickly. I got in via Facebook. I have a facebook artist page and I post work there. Do this a lot, 1 per day, no more. Eventually, your craft spreads and some people will notice you. This can take a long time. I live, by choice, in an artist colony town. The summer population is about 30,000 people and we have about 70 galleries in town. Being part of an artistic community helps. Be active in it. Meet people. Always have your iPhone on you with a small sample of your work.
I knew that a gallery owner liked my work so I approached her, asking for advice on how to get into galleries. (I did not expect to get into hers, she only carried painters as far as I knew.) She told me that I should not blast my portfolio to all the gallery owners. I needed to do my homework and know which galleries would take photography and which would take my type of photography.
She had me assemble a portfolio of about a dozen pieces, printed, and matted. This is what you present to the gallery owner. This process is difficult, you love all you work but you really need to winnow it down.
I had a trial run with her, showing her my portfolio. I was stunned when she told me she wanted me in her gallery!
So in that case, one of her pieces of advice was wrong, but only sorta. I had discounted her gallery because she didn't carry photography. But that was only because she didn't have any she liked. She carried images of vibrant color. So, you need to find a gallery that likes what your work is like.
If you don't know someone who knows your work I would guess the process is much harder. Again, you need to build a portfolio but cold calling galleries with the case slung over your shoulder is likely not to work and it will take a very long time. I would produce a DVD of my work and start mailing that to owners. Put together an artist statement, an artist CV etc... Again, I'm just guessing here.
And finally, it is tough being a photographer in a field dominated by painters. Many galleries only carry paintings. But as my case showed, you can break in if your style fits. I've also noticed that a large amount of galleries that carry photography only carry B&W photography. This may or may not suit your style.