Friction is an adhesive process. When you touch two surfaces together the atoms at the two surfaces come into contact and form interatomic bonds. In the extreme case of very clean and smooth surfaces you can get cold welding.
So reducing static friction is basically a matter of stopping the surfaces from adhering to each other. For example applying a thin (i.e. molecular dimensions) layer of oil or grease will make the contact an oil-oil contact instead of iron-iron (or whatever the materials are made of). Even an adsorbed monolayer such as a surfactant will reduce adhesion, and many lubricating oils contain surfactants such as molybdenum dithiocarbamates and zinc dialkyldithiophosphate for this reason.
I take slight issue with Floris, because it's usually only possible to form the sort of oil or air films that he mentions when the surfaces are in motion i.e. the friction is dynamic. When relative motion is stopped the separating films will normally drain away and the surfaces will come into contact. Under these circumstances you need some material of the sort I describe above that will reduce the adhesive forces between the surfaces.