'AF' is a generic abbreviation for autofocus. But within the Nikon SLR/dSLR system, 'AF' refers to lenses which are focused by a motor in the camera body. While AF-S refers to lenses which are focused by a motor system in the lens. AF-S is a newer system, which allows for quicker and quieter focusing.
Both AF and AF-S lenses should work with all autofocus Nikon SLRs. However on a D40 or D40x, AF lenses (as opposed to AF-S) will not autofocus, because those cameras don't have the motor in the body. On all other autofocus Nikon SLRs, both AF and AF-S lenses will autofocus.
S is the designator for Silent Wave Motors. It should be mentioned because some other manufacturers put motors in their lenses which are not faster and quieter than the one in the Nikon camera body.
Silent Wave Motor (UltraSonic Motor for Canon, or HyperSonic Motor for Sigma) is a piezoelectric system powered by crystals excited with current rather than the traditional magnetic flux exerting torque on a shaft.