First check that in Configuration > Sessions the following are all set to false:
Force Cookie Use
Check SSL Session ID
Check User Agent
Check IP Address

If it's still not working after that look at phpinfo.php and check that the following are turned off:
register globals
magic quotes
session.use_trans_sid

That's just my two pence. No doubt there are many other settings that might be involved.