Where should I add the unique identifier cookie code? I want to add a unique identifier in a cookie when the user (anonymous or logged) visits the website. Where should I call this code. I tried calling the code in hook_init but that doesn't work on cached pages. Any help would be greatly appreciated. Thanks.
I think hook_boot() would be the best place for your code:

This hook is run at the beginning of the page request. It is typically used to set up global parameters which are needed later in the request.
Only use this hook if your code must run even for cached page views.This hook is called before modules or most include files are loaded into memory. It happens while Drupal is still in bootstrap mode.

(emphasis mine)