I like PeelBoy's suggestion.
I see no need to move everyone to sessions, just those who can't/won't use cookies.
It's a simple matter to tell if a user is accepting cookies--attempt to set a test cookie, refresh to another page that checks if that cookie was actually set. If it was, continue as normal, if not, switch over to sessions.
That gives the cookie-less people an almost identical experience to the rest of us. I suppose you could have an option somewhere of "cookies or sessions", but I don't think that's really necessary--if someone doesn't want to use cookies, they can just turn them off themselves.
