PG, Since you didn't fill out your profile or explain what kind of work your wife does it's a bit hard to know where to begin. An awful lot depends on where you are and what your wife photographs. Does she do landscape? Street? Architecture? Archaeology? Abstraction? Surrealism?
If you're in New York City, San Francisco, or Santa Fe, the approach might be a bit different from the approach you'd use in, say, East Podunk, but you always start by going through the galleries and seeing what they're showing. The thing you have to remember about a gallery is that it's in business to make money, and if the gallery's been around for a while you can be pretty sure the stuff it's carrying is what sells in that area, and therefore, what the gallery's willing to accept to hang on the expensive space on its walls. If the kind of work your wife does isn't the kind of work the gallery hangs, the fact that her work is amazing won't cut it. Look for another gallery.
Once you find a gallery that carries the kind of work your wife does, the next thing is to find out who the gallery's decision-maker is. You'll probably be spinning your wheels if you simply bring in a portfolio and plop it down in front of a clerk. On the other hand, unless you're in the art district of a large city that probably won't be a problem because in a smaller town the gallery owner usually will be the person on duty. But it's not only intelligent, it's polite to begin by finding out whom to talk to.
There are many ways to make up a portfolio, and how you do that will depend a lot on what kind of work your wife does and what kind of gallery you're approaching. 13 x 19 inch prints in a leather-covered presentation case can be effective. Even more effective might be a few appropriately sized prints mounted, matted, and inside clear bags. I say "appropriately sized" because what's appropriate depends on the subject matter. If your wife's doing landscape you probably want large, very sharp prints -- at least 13 x 19 in 20 x 26 mats. If she's doing street, 8 x 10s in 11 x 14 mats probably will do the job. One thing that a few precious galleries seem to indulge in is the tiny print in a huge mat: say, a 2 x 3 print in a 16 x 20 mat. But that kind of matting requires a particular kind of print and a peculiar attitude toward what constitutes art.
It's extremely unlikely that a gallery will buy your wife's prints outright, so if a gallery accepts her work they're going to accept it on consignment. A consignment contract will require you to deliver a finished product: either mounted, matted, and bagged prints or framed prints, or both. A top-of-the-line gallery will insist on conservation (archival) framing. If the prints are mounted, matted and bagged the mounting and matting should be done with archival materials. Since, at this point, your wife is an unknown with an unknown sales potential the gallery will require at least a 50% commission, possibly more.
I could go on and on, but to get an accurate picture of the pond you're about to jump into pick up a copy of Brooks Jensen's book, "Letting Go of the Camera" and read it. You didn't give us an idea of the background of the people included in "everyone who has seen her shots," but you have to understand that when you consider the average quality level of photographs in general "amazing" is a common response to a fairly good photograph.
I don't mean to sound too discouraging. I can guarantee that a successful gallery is always looking for inventory that will sell, and if your wife's photographs fit that category for the gallery, they'll snap them up. On the other hand, since you mention a "showing," rather than gallery representation, have you considered other ways to present her pictures? You might look for local art shows, art shows at county fairs, hangings on library walls, etc., venues that might get her work before the public. That kind of thing is a lot less steep hill to climb.
In any case, good luck. You might want to put one or two of her pictures on LuLa so we can see what you're talking about.