What does a search engine 'see' when it enters your site and spiders without sending the 'language' cookie? That is the question you need to answer -- by using a browser or 'tool' with cookie support disabled to test your site. It is most likely that your site won't work, or that only one language version will be accessible.
If you are not happy with your test results, then yes, it's important.
Remember that search engines only know about URLs; They don't consider 'sites' or 'pages' or anything else -- The only 'object' that they recognize is a URL. So, if the URL doesn't change based on the language, then only one language/page will be 'seen' at any one time, and only that language/page will appear in search results.
So consider putting the language-code in the URL -- either as a subdirectory, as a country-code domain, or as a subdomain of your main domain.
When considering problems like this, take a look at how the search engines themselves do things, since it's likely they wouldn't do anything that would cause their own sites to have problems in their own search engine. There's a good reason that Google uses country-code domains...
Jim
