The below answer was written a long time ago. Now, for better or worse, due to laws in various countries it has become either good practice - or a legal requirement - not to require cookies except where necessary, at least until the user has had a chance to consent to such mechanisms.
It's a good idea to only do this when the user is trying to do something that initiates a session, such as logging in, or adding something to their cart. Otherwise, depending on how you handle it, you're potentially blocking access to your entire site for users - or bots - that don't support cookies.
First, the server checks the login data as normal - if the login data is wrong the user receives that feedback as normal. If it's right, then the server immediately responds with a cookie and a redirect to a page which is designed to check for that cookie - which may just be the same URL but with some flag added to the query string. If that second page doesn't receive the cookie, then the user receives a message stating that they cannot log in because cookies are disabled on their browser.
If you're following the Post-Redirect-Get pattern for your login form already, then this setting and checking of the cookie does not add any additional requests - the cookie can be set during the existing redirect, and checked by the destination that loads after the redirect.
Now for why I only do a cookie test after a user-initiated action other than on every page load. I have seen sites implement a cookie test on every single page, not realising that this is going to have effects on things like search engines trying to crawl the site. That is, if a user has cookies enabled, then the test cookie is set once, so they only have to endure a redirect on the first page they request and from then on there are no redirects. However, for any browser or other user-agent, like a search engine, that doesn't return cookies, every single page could simply result in a redirect.
Another method of checking for cookie support is with Javascript - this way, no redirect is necessarily needed - you can write a cookie and read it back virtually immediately to see if it was stored and then retrieved. The downside to this is it runs in script on the client side - ie if you still want the message about whether cookies are supported to get back to the server, then you still have to organise that - such as with an Ajax call.
For my own application, I implement some protection for 'Login CSRF' attacks, a variant of CSRF attacks, by setting a cookie containing a random token on the login screen before the user logs in, and checking that token when the user submits their login details. Read more about Login CSRF from Google. A side effect of this is that the moment they do log in, I can check for the existence of that cookie - an extra redirect is not necessary.