This is a technique for making softer shadows when doing shadow mapping. It works by filtering the result of the depth comparison. So when comparing a depth, some depths around should also be compared and the result should be averaged. This will give a softer look on the shadow edges.

It can be implemented as simple as this in a the pixel shader:

float result;
result = shadow2DProj(shadowMap,texCoord+offset[0]);
result += shadow2DProj(shadowMap,texCoord+offset[1]);
result += shadow2DProj(shadowMap,texCoord+offset[2]);
result += shadow2DProj(shadowMap,texCoord+offset[3]);
result /= 4.0; // now result will hold the average shading

The samples are often either taken in a grid-based square around the original sample location or randomly scattered around it.

Optimization:

NVIDIA has built in hardware support for doing bilinear interpolation between four samples.

ATI has fetch4 which will fetch four texture samples at the same time.  

The original paper for PCF:
http://graphics.pixar.com/library/ShadowMaps/paper.pdf

A technique that is similar (percentage-closer soft shadows)
http://developer.download.nvidia.com/shaderlibrary/docs/shadow_PCSS.pdf

A paper including lot’s of shadow mapping information, including different ways to do PCF (the image in this article is borrowed from this presentation):
http://developer.amd.com/media/gpu_assets/Isidoro-ShadowMapping.pdf