You probably would be best off using a single CGI program to handle all stages. Aside from your original cookie issue, it cuts down on duplicated code (e.g., initialization) by allowing all stages to reference the same routines and also makes it much easier to repeat stages if needed. (User ended up at stage 3, but some of the required information is missing? Just call the stage 2 sub and send them back to fix it.)
Personally, I tend to use a CGI::Application-style approach to do this, with the code for each different page of the application in a separate module, then a very small .cgi which just loads up those modules and dispatches calls to them based on the request's specified action (CGI::Application calls it a "runmode"). Others are very fond of Catalyst or other frameworks, but I'm not familiar enough with any of them to describe how they function.
Oh, and I just reread your post and picked up on something I missed earlier... Are you under the impression that "1 CGI script = 1 page"? That is most definitely not the case. The same CGI can produce an unlimited number of distinct pages. Having a single CGI program which produces 6 different pages (selecting based on the input received - or selecting randomly, for that matter) and saving each one's input to the database after each step is no harder (and probably actually easier) than writing 6 separate CGIs which each produce one page.