have a splash page or something which supposedly tries to set a cookie. Then this page will redirect the users to the actual page where cookies are used. If the next page finds the cookie (set by the previous page), then cookies are working. If not, you can complain to the users or provide an alternate.
e.g.
page1.php
...code...
setcookie("supportcookies", "yes", time()+300);
... print link to next page...
...rest of code...
page2.php
if($supportcookies) {
print "yay, you have cookies";
... rest of code ...
}
else {
print "sorry, can't visit site";
... or provide alternate code w/out cookies...
}
hope this helps,
-sridhar