Instead of sending the data in the cookie, save the data to a database with a randomly generated session ID (I usually use Data::UUID for this). The ID is simply put into the URL string, e.g.:

http://www.example.com/your_program.cgi?id=abcdefg
[download]

When the CGI runs, it grabs the session ID value off the parameter list and get's the saved data from the database. If the user is using a form, you can put the ID in a hidden field instead.

You should be using this method even if you use cookies instead (by putting the session ID as the cookie value). I've rarely seen a good excuse for not doing so besides sloppy coding.

There are various modules for helping you do this. I've heard of CGI::Session before, but I've never used it, so I won't comment on it.