>How would you know you sent a cookie to them already?
>

Just send the cookie on a page with a meta refresh tag in it that points to a page which tests to see if the cookie has been received. Or, add JavaScript to the page that reads back any written cookies - if the script doesn't find the cookie, it can navigate to a new page (or just display on the current one) to notify the user that cookies might be required.