Actually, there have been a number of reports that stretching does may be more of a hinderance as opposed to helping when working out...in weight-lifting anyway. For cardio type exercise I would recommend light stretching so you don't pull anything. For weight-lifting, a slow, concentrated warm-up set is all you need.
But for SORENESS after the gym, it really depends on what you're talking about. Are you talking about just general soreness and tiredness that you get that same day? Or are you talking about severe soreness that you get two days after working out (commonly called DOMS, Delayed-Onset-Muscule-Soreness). Some people say take glutamine, I don't buy it. I say...you're lifting too much too soon.
Working yourself to complete exhaustion is great, fun, I love it (when I used to work out), BUT it sounds like you're just starting to get into the gym. You're body isn't use to what you're doing (even if you've worked out in the past).
So my advice, gradually build up the intensity of your workouts.