Как на php определить включенность cookie?

Такое проще сделать на javascript.
Для новых браузеров: if (navigator.cookieEnabled) return true;

Для старых:

// set and read cookie
document.cookie = "cookietest=1";
var ret = document.cookie.indexOf("cookietest=") != -1;

// delete cookie
document.cookie = "cookietest=1; expires=Thu, 01-Jan-1970 00:00:01 GMT";

return ret;

Если на php то так:

<?php
session_start();
setcookie('foo', 'bar', time()+3600);
header("location: check.php");

и check.php:

<?php echo (isset($_COOKIE['foo']) && $_COOKIE['foo']=='bar') ? 'enabled' : 'disabled';

В 2 запроса к серверу
1. поставить куку
2. проверить есть она или нет

В первом запросе кука только отправляется на клиент, поэтому до следующего мы не знаем сохранилась на клиенте кука или нет.

PHP + JavaScript + Ajax
На странице, которая показывается пользователю, JS определяет наличие куки и отправляет инфу на сервер через Ajax (фактически это будет второй запрос к серверу).