Use sessions when they are appropriate.
Our fellow mod @EAMann has written a useful session class for exactly these cases. There is a plugin described here that offers a different API.
Just make sure to start the session only when you really need one. Google and other crawler don’t accept cookies, so you would end up with lots of duplicated URLs indexed like this:
/postname/?sid=123455667889