Look at Apache::Session module. It works for me in Apache/mod_perl environment, but I think it could be used in CGI too.
Some Web application frameworks have their own session mechanisms, so maybe you want to consider using some of these frameworks instead of plain CGI. Look at the Web Application Framework thread.