I’ll try to re-explain what Richard has already explained:
The issue is that there is a difference between subdividing, and subsurfing. Subdividing takes each face, and finds the mid-point of the edges, and then cuts the face into four pieces. To do this it creates five new vertices, one on each of the old edges, and one in the middle. It places each of these new points ON THE ORIGINAL FACE. Thus, although you have extra geometry, your face is as flat as it was.
Subsurfing, however, creates the new points, but places them on a curved surface, dependent on the normal at that location, so that they all follow the theoretical curve that the original face was mimicking.
The rendering of a face, regardless of gouraud, or any other method, takes the normal at each corner of the face, and smooths the apparent normal across the face. However, if you have subdivided the original face, the faces in the middle of the original face are all parallel to the original face, and have all of their normals pointing in the same direction, so they will look flat. Only those faces that are immediately adjacent to the original edge will have their normals pointing in different directions, and thus only those faces will be shaded as ‘curved’. The more you subdivide the faces, the narrower a band around the original facet will be ‘curved’, and thus the edges will become more and more noticeable.
Subsurfing not only interpolates the points onto a curve, but also interpolates the normals onto the curve as well, so the surface becomes smoother, the more you subsurf.
You can see this if you apply a subsurf to a cube. It will become a sort of sphere, but as you subdivide the cube, it will more and more closely resemble a round edged cube again.
The smoothing is dependent on the angle between the faces. Angles sharper than the autosmooth setting will not be smoothed. Also, to apply smooth, you have to be in edit mode and have the faces/edges selected.