It's probably safest to both set a cookie and also put it in the query string. That means modifying every link you generate for the user.

Of course, that gives you really long and ugly URLs with a lot of noise in them.

So the first time you receive user's session ID in a cookie, you could set a "cookies work" flag in the user's session. From then on you can stop adding the session ID to the links you generate. If the user loses the cookie, you start them over with a new session.

Another strategy would be to start by assuming that cookies work. The first time you receive a cookie-less request for any page that isn't the main entry page to your site, you start adding the session ID to the query string.