PHP session info is stored in a text file on the web server, in the directory specified in your php.ini file. The php session cookie stores the session Id on the users local HDD (obviously) so that the web server knows which session file to associate with a particular request.

I've not worked with a load-balancing environment, so I'm not sure how the web server handles distributing the PHP session file across the web servers in the farm, but I'd assume this is where the problem comes into play. In other words, if one request goes to one server, and a subsequent request goes to another server do the servers transfer the session file back and forth?