I have website with multiple languages and at first entrance it checks for cookie and if no cookie is present then it defaults to English language and redirects to example.com/en.
So basically every time someone enters example.com he will be redirected to example.com/{language}. Is this bad for SEO?
The problem with your set-up (from an SEO standpoint) is that search engines don't accept cookies, so whenever a bot follows a link to your root domain, it'll be sent to your English content. Hopefully, there's an abundance of links to the other language content, too, but in my experience, this situation nevertheless seems to lie at the root of a lot of geotargeting difficulties.
This might be why Google recommend that you "Avoid automatic redirection based on the user’s perceived language. These redirections could prevent users (and search engines) from viewing all the versions of your site."
I have a client whose /en/ pages (they have umpteen other languages on their domain) show up for most searches globally, despite there being good region-specific alternatives, and despite employing Google's rel="alternate" method. The only remaining cause appears to be that they default to /en/ at root in the absence of an Accept-Language HTTP header (search engines don't usually send one).
In short, I'd be inclined to allow users to manually choose their language and then set a cookie, rather than redirect.
en pages show up for keywords in another language?
/en/ pages show up for most searches globally as I thought you meant e.g., users in cn using keywords in zh-hans got en results, despite there being good zh-hans-cn alternatives.
As of Jun 10, 2014 Google recommends either ccTLDs, Subdomains with gTLDs or Sub-directories with gTLDs. URL parameters such as ?lang=en are not recommended:
https://support.google.com/webmasters/answer/182192?hl=en#2
(Funny that the page which says that it's not recommended to use URL parameters for this, is actually doing exactly this.)
Generally speaking, re-directing the user on page load is never a good thing. It's called a doorway page. However since this is with regards to auto-selecting the language, there shouldn't be any problems.
I myself prefer a different solution than re-directing them to /en/ or /de/, and that is to re-direct to /?lang=en instead. Since this signifies that it's the same physical page but with a language variable selected, it's not viewed as a re-direct in the strictest of definitions.
I honestly couldn't tell you whether that's better or not for SEO though.
I assume that when somebody visits site.com/de with no cookies they still get the German version?
Other than that caveat, I don't see anything wrong with it from an SEO standpoint.
You could also consider redirecting based on the user's "Accept-Language" header that is sent by the browser. Here is somebody that uses some php code and mod rewrite to make it happen: https://stackoverflow.com/questions/1661915/how-to-redirect-based-on-accept-language-with-apache-mod-rewrite
