The Great Outdoors Stack Exchange is a question and answer site for people who love being outdoors enjoying nature and wilderness, and learning about the required skills and equipment. It only takes a minute to sign up.
Personally you don't need to go for any of the name-brands, unless that is important to you.
Some things to look for:
Comfort. Wear them for several minutes. Yes, the salesman is trying to wrap up this sale in under 2 minutes so he can get more commission. You will likely be wearing the shades for hours on end, so keep them on for at least a couple of minutes before deciding you like them.
Viewing area. I tend to prefer large lenses because when I wear smaller lensed sunglasses, the area surrounding the lens is much brighter, and as a result distracts me from where I'm trying to look. It also tends to give me headaches from the stress/strain. And since your pupils will dialate, they also let more UV light into your eye
Polarization. Some folks love polarized lenses (I'm one of them), others hate them with a passion. I like polarized lenses because it cuts down on reflections and glares. If I'm looking at a lake, I'll see the reflections in the water, but if it's the sun, I won't see sunlight reflecting off of every ripple of water and in come cases/angles, it gets rid of the reflections entirely. Great if you are fishing, because you can see the fish/stuff in the water, great while driving because instead of reflection rays from bright parts on cars, it will be reduced to a single very bright spot. The downside is that when you look at some things (plastics come to mind) you will sometimes see rainbow haloes in the clear plastic object and not be able to see through it.
Black/Grey or Brown tint. Some folks like the black/grey tint (which won't affect color balance much), others prefer brown tint (which I find makes everything look more yellow). I have both. My eyeglasses have grey tint in the transitions, I also have sunglasses for driving and other long-term outdoor stuff that have the brown tint. I find that I prefer the grey tint, but not enough to say that I want gray and won't consider brown. I'm sure there are other tint colors, but I've not seen them avialable (since I do my sunglass shopping at the Optometrists, they sometimes lag behind the Sunglass Hut when it comes to new products).
Corrected Lenses. I have a minor prescription (I believe it's -1.75, 0 is "normal" vision, 10 is sightless IIRC, and 7 or 8 is "legally blind"). I can function without my glasses if I had to. In fact, I used to DRIVE with uncorrected sunglasses from the El Cheapo rack at the drug store. Then I had some extra cash (flex account) and splurged on prescription sunglasses. WOW. What a difference. If you wear eyeglasses, I Highly recommend you get the "second pair" of glasses and get prescription sunglasses.
Those large sun glasses that are used after cataract surgery are great - stops 100% of all types of uv and completely covers your eyes. New $70, used $5 at charity store or just take your mums. Yes, you will look like an old person and they are breakable plastic, but for $5, buy 2.