One thing I would definitely look for is someone who does not practice (or encourage you to practice) "steady-state cardio" i.e. doing walks (or runs) at the same speed for 30 minutes. Many gym-goers are still working out this way (long, slow runs on the treadmill), but it is considered passe by trainers who keep up with recent developments.
One article as food for thought: http://www.strengthcoach.com/public/1766.cfm
Another thing I would definitely look for is a trainer who believes in doing mostly compound exercises (multi-joint movements) for strength training. The whole isolate-each-body-part (training like a bodybuilder) has also gone by the wayside over the last ten years or so in the fitness community. So, anyone who encourages you to do bicep curls, and then do some tricep extensions, and then do a quadriceps extensions -- that's probably someone who has been training the same way since 1997.
You want someone who has you doing the "big" exercises, like some type of "push" exercises (incorporates chest, triceps at once), some type of "pull" exercises (to get back, lats, biceps at once), some type of squatting movement (hip, glutes, quads, etc.), and so on.
AND someone who incorporate all of the above into a safe program for your level, and for your age, and for any past injuries you may have.
Even if you are a beginner, I think it would be criminal to train you with 1995 best practices.
I think (and please excuse me for "going off" on this topic for a bit!) that many trainers give people what they want, which is to encourage them to do the things they already want to do, which is to do long, slow walks (or runs) on the treadmill for supposed "fat burning" and to do strength training that let's them sit on the machines and doesn't get them too out of breath.
OK, that's it for now. Please don't let any of my advice scare you off. You can do this!