Depends on whether or not you need to check against WordPress’ user authentication. If you need to know whether they’re a logged in user, hook onto 'init'. Otherwise, the sooner the better.
If it’s something that should fire on every page load, and only checks for existence of the cookie and doesn’t need to tap into any of WP’s APIs, I’d put it into a custom MU-plugin named 0000a.php to ensure that it fires before any non-core files could accidentally send headers.