An explicit representation, for example, describes a line as the straight segment going through two given points. A procedural surface is one which is defined as a procedure.
For example, in CAD/Computer-aided manufacturing milling applications, an offset surface is a procedural representation because it is defined as the surface which is a fixed distance from another surface. Another well-known procedural edge on a 3D body is the silhouette edge. This edge is defined as the collection of points on a surface whose outwards surface normal is perpendicular to the view vector.
Another example of a procedural surface is a Blob as illustrated in movies like The Abyss in the scene where the creature made up of water reaches out and touches the character. The surface is defined as a surface which exists when two or more control points are oriented in such a way as to make the contribution potential exceed a certain threshold. Such procedural surfaces require far more processing to calculate, and for this reason are often used in pre-rendered rather than real-time applications.