With Per-vertex shading/Gouraud shading each pixels intensity gets an interpolated intensity based on the intensity of each of the 3 vertices in a triangle. In the Cg-toolkit there is a vertex program for per-vertex shading. But since this program is run for each vertex I assume that the interpolation does not appear in the vertex program. But where is the interpolation executed - in the rasterizer (which is currently not high-level programmable)?

Yes, the interpolation of the other attributes are done along with the vertices during rasterization.