In addition to @Tester101's advice about clean joints, you also need tight joints. In general, most glues need to be squeezed to a very thin layer to obtain maximum strength.
In many new chairs, there is cut in the end of the stretcher tenon. A very thin wooden wedge is coated with glue and is driven in that cut to expand the end of the tenon and lock it into the mortise. This is sometimes a blind wedge (if the tenon does not go all the way through the leg) driven in by hitting the end of the mortise pocket. Sometimes the mortise goes through the leg and the wedge is driven from the outside and then trimmed flush. These techniques give the tight fit that enhances the glue bond and creates a better mechanical fit as well.
The problem with many stretcher repairs is that the mortise hole in the leg has been expanded by shifting and rocking of the tenon. A close fit then becomes impossible.
What you may have to do is tighten the fit of the tenon. You could build up the mortise by gluing in shims and then shaping them to make a tight fit with the stretcher. This is fairly hard to get exact unless you really build up the mortise and then redrill it with a drill press. It may be easier to insert the stretcher and then tighten the fit by driving in very thin hardwood shims alongside the stretcher tenon. The shims should also be coated with glue.
Screw attachments through the leg into the end of the tenon was a fairly common attachment technique on lower end furniture in the late 19th, early 20th century. It was also a fairly common repair technique. However, A screw in an end grain, especially one experiencing both expansion pressure (pulling straight out) and lateral shift is a fairly weak connection. But if other techniques fail or are too hard, it might hold for a while (maybe even a decade or three).
