Actually, the lens influences the focus in two ways:

1) The speed with which it focuses (speed of its motor)
2) The amount of light it gathers (linked to f stop)

Obviously, the faster the focusing motor and the more light a lens gathers, the faster it will focus. But the focus confirmation and seek is also dependent on the camera you use, which can bring inconsistencies between various camera+lens combinations.

You can fit a 24-70 f2.8 nikkor lens (damn fast lens) on a D40 which has about 3 autofocus points and a relatively simple focusing system, and it will still focus pretty fast; HOWEVER, it probably won't get the focus right every time, because of the simplistic nature of the camera's autofocus system.

If you stick the same lens on a D300s or above, which has probably more than 50 autofocus points and a much better processor/system to make use of all of them, you will get much less badly focused ones.

Answering your question: AF lenses (Nikon) are lenses without autofocus motor, they focus by turning a screw on the lens mount - the camera does all this, and only the semi-pro or above models do it (d90 or better). AF-S lenses have a motor built in, they autofocus on all modern cameras, even cheap ones.

I don't know the precise differences between the performance of these two kinds of lenses, but as newer, and more expensive lenses all have dedicated AF-S motors, i assume that a dedicated focus motor improves performance.