En principio da igual quien envía el header, pero hay que enviarlo, porque es la respuesta normal de una petición HTTP. Lo principal es crear la cookie de la sesión. En el ejemplo que te he dado NO se utilizan cookies, sino que se pasa en el URL de la petición. CGI::Session lee, en el segundo programa, el número de sesión, lo recupera, y sabe el nombre de la persona. Pero yo creo que no está bien hecho, porque accedo diréctamente al parámetro CGISESSID, cuando todo eso debería ser automático.
Lo mejor será leer el CGI::Session::Tutorial.