¿Como saber si las cookies están habilitadas del lado del cliente?

Esto se puede comprobar en el Javascript con el objeto con la propiedad cookieEnabled del objeto navigator.

function are_cookies_enabled() {
        var cookieEnabled = (navigator.cookieEnabled) ? true : false;

        if (typeof navigator.cookieEnabled == "undefined" && !cookieEnabled) {
            document.cookie = "testcookie";
            cookieEnabled = (document.cookie.indexOf("testcookie") != -1) ? true : false;
        }
        return (cookieEnabled);
    }

También se puede saber creando una cookie y comprobar si el navegador lo hizo o no.

Fuentes:
http://stackoverflow.com/questions/2167310/how-to-show-a-message-only-if-cookies-are-disabled-in-browser
http://stackoverflow.com/questions/531393/how-to-detect-server-side-whether-cookies-are-disabled
http://es.softuses.com/70356