Not using sessions or cookies just because of seo is not a good idea. Just think if a user comes to a site from a search engine and has problems using it then you will lose some traffic (I almost left because the firefox adblock block images from this site).
Using sessions or cookies alone is a problem for seo, but using it in combination with other methods shown above gives a more user friendly experience and gives you the benefit of seo.
Although I think too much seo does bring down your rankings.
Focus more on the user experience and content, that will most likely be more weighted by users