When you initialize a session, php sends a cookie automatically in the header response. The cookie only contains the $PHPSESSID. It doesn't contain any data you may be storing in the session. If you want to code for users that have cookies disabled you need to pass the session id via the url. This is still no big deal as every session id is different therefore solving your search engine issue. When the spider comes to crawl...it will be assigned a unique session and won't deal with other clients cart contents.
(of course you could use Robots.txt to ask spiders to not crawl "/order.php"....bad robots will disregard it but still...google won't hit it every week.)
So if your cart url is .."/order.php" you can just make it "/order.php?PHPSESSID=$PHPSESSID". If the session is not started (assuming you have session_start() on "/order.php") the server will start a new session with a unique session id otherwise session_start() will resume a existing session.
That said...most people who do any online shopping will accept cookies as it is fairly standard for developers of shopping carts to use em.(even though maybe they shouldn't count on em.)
The beauty of sessions is that they can't be spoofed as easily as the session_id is unique and the data is stored on the server rather than on the client.