...from the male perspective. Buying lingerie for yourself (from the male perspective) is not something I have experience in but I heartily encourage someone else to node.
Don't ever be embarrassed to walk into a lingerie store. Some men can be a bit nervous walking into a store full of the most intimate intimates loaded mostly with women and containing only female sales associates. What you need to remember is that these are friendly and helpful sales associates who want your business and your money. Mostly your money. She will give you all the assistance you need and then some, with a smile on her face, doing everything she can to make you comfortable when you're out of your natural environment. She will also not judge your decision, personality, or bedroom life no matter how slutty you're planning to dress up your girlfriend. At least not to your face.
The other women in the store will be doing their best to avoid eye contact with you. You can safely ignore them. In fact, they're probably hoping you will return the favor and avoid eye contact with them. No one is going to step out of the dressing room to ask "Do you think my boyfriend would like this?" unless you're living in a porno movie.
If for whatever reason you are made to feel uncomfortable, just try another lingerie store and hope for more cooperative employees. You probably just hit a rare bad one. They don't deserve your money. If all else fails, you can always get her a gift certificate and let her pick out something, but that's probably a last resort.
Do not be afraid to admit ignorance! Even if you're the kind who refuses to stop to ask for directions on the highway, it's okay to admit you're not an expert in women's undergarments. In fact it's probably a little creepy if you are. If you've never bought lingerie before, talk to a sales associate and say so. She will tell you what you need to know, and if you need more information than you happen to have she'll happily wait for you to come back tomorrow or the day after with your measurements and credit card. For some lingerie all you need to know is your girlfriend's height and bra size. For others you may need to use a tape measure and a set of calipers, although in these cases it might be easier just to bring your girlfriend in to try it on.
If the lingerie is a surpise gift for a special occasion and this is your first purchase, you may need to be sneaky to find the measurements you need to get the right size. The complications here are numerous and quite frankly, you've never been able to keep a secret from her so you're probably just fooling yourself if you think she's not picking up on the hints you don't know you're leaving. Oh yes, she will know that you've been digging around in her underwear drawer.
My advice is to make your first lingerie purchase without trying to surprise her. Just tell her what you're planning and get her measurements from the source. If you're buying sexy underwear for her, you should probably be at a comfortable point in the relationship for this. Just remember to make a mental adjustment for the inevitable... er... low-end estimates of her measurements. Once you've gotten the first set, you should have all the information you need to make your next purchase a surprise. If she's not comfortable enough with her body to give you her measurements, is she going to be comfortable enough to model the lingerie for you? Actually she might be, women are complicated creatures that we simple-minded men will never have a hope of figuring out.
When you're ready to pick something out, think about what your girlfriend's best assets are, and remember that an ineffectual covering is often sexier than a nude body. Is she built with a nice curvy waist and hips? Does she have long, luxurious legs? Possibly blessed with a bountiful bosom? Whatever she's got, you want her to flaunt it, so look for something that accentuates those features. Something with a high-cut hip is good for the legs, as are garters and stockings. A belly-baring design can help bring out her waist and flat tummy. And depending on taste, either a plunging neckline or something that covers her top completely can make the breasts a joy to unwrap.
Paraclete helpfully pointed out that there's another side to this; lingerie is just as much for her as it is for you. To get the most out of dressing her up sexy, she's got to feel sexy and confident, so don't try to make her show off anything she doesn't want to. Most women aren't 100% comfortable with their bodies, as an unavoidable result of being constantly bombarded with images of artificial feminine perfection by the media. So if she's sensitive about, for example, a little extra in the tummy region, something that covers or even helps control the midsection might be the best selection.
Keep in mind that there are two kinds of lingerie stores out there (not counting the lingerie section at Sears), which I will broadly divide into Victoria's Secret and Frederick's of Hollywood. Stores like Vicky's will have higher-end, pricier, and classier merchandise for treating your woman like a lady in the bedroom and a whore in the kitchen. Frederick's-style stores will have lower cost and quality, and generally be sluttier fare, but may have kinkier items better described as costumes than lingerie. These are for treating your woman like a whore in the bedroom and the kitchen. The decision is a personal one, but a healthy relationship with open and honest communication should help you figure out what you need.
But whatever you do, remember: feeling the material is expected, but try to stop short of fondling the undergarments. Do not leer creepily at anyone or anything in the store. And never, ever ask if something comes in children's sizes.
One final bit of advice for you young lovers and cheating partners: When running off for a midnight tryst at a cheap motel the basic idea is to not get caught by your parents or lawfully wedded spouse. This means that you can't exactly take the lingerie home and toss it in the washing machine. Better safe than sorry, you know. Now of course any article of clothing in close contact with the crotch is going to get a bit messy, so they will need to be cleaned. What to do? Many lingerie stores sell small, easily concealed bottles of lingerie cleaning detergent, a mild detergent good for delicates. Get a bottle of this and wash your evidence in the hotel's sink or bathtub before you leave. Keeping the bottle and lingerie hidden from prying eyes once you get home is your problem.