buenas...
no es tan complicado de hacer, lo único que necesitas es un manejador de cookies. la técnica que utiliza es bien simple. primero se crea una cookie, el valor no importa. luego para determinar si se limpiaron las cookies, simplemente tienes que verificar si existe la cookie que se creó. un ejemplo de un manejador de cookies que podrias utilizar
http://www.quirksmode.org/js/cookies.html#script
esto implica que no hay manera de detectar si realmente se borraron todas las cookies del navegador. javascript no puede determinarlo porque el script se ejecuta en el contexto de un sitio web y solamente tiene acceso a las cookies de ese dominio.