(2) Don't try to shove cookies down peoples throats on every single page. Some people have cookie warnings turned on and this makes your site almost unusuable to them. Ideally you should try to give them a cookie one time and never again (for that session).
(3) Ideally you have a database to keep track of your users, so the only cookie you ever need to give them is their user ID cookie, which is usually a big number. Then all the data you want to track can be kept in the record. This is better (for several reasons) than stuffing all the data into their cookie cache.
(4) Make your site "non-cookie friendly." Let your cookie users reap the benefits of cookies, but non-cookie users should still be able to use your site.
If you want to start looking at actual Perl code lets take this discussion over to the server-side scripting forum...
OK, I hear you. So suppose your database gives them a user number, like 12345. You have a script called offwego.pl which basically sets a cookie called ID to 12345 and presents a big link, "Click here for PayPal." Then Pay Pal sends them back to a script called welcomeback.pl which checks for the cookie and sends them where they need to go. Anticipate a surprisingly high % of people to come back without a cookie, so you'll have to decide how to handle those people too.
There are ways to do this entirely in Java without using CGI at all. I don't advise it, that's just another layer of stuff that can break for some people.
So go to your Linux prompt and type "perldoc CGI" and read the section on cookies. You'll see lots of examples; it's pretty easy stuff.
A follow up note: for security purposes, it might be good idea to generate another random number and add it to their user ID. E.g., you set the cookie to 12345-301924597
Then on the way back, you make sure that random number matches the one you gave. The reason for this is that otherwise, somebody could impersonate somebody else by entering your welcomeback.pl script with a "forged cookie." If you're worried about that.
Why the reliance on CGI.pm? I find it slow and difficult to use. Additionally, I worry about it as a potential security hole - if everyone is running it, that just gives hackers more incentive to investigate potential holes.