I think the issue was, my php folder is under a different directory apart from html page.
I went through the php documentation about cookies, and found out that Cookies can be saved for specific page which is depending on the path you specified.
What I did changed right now is specify the path as '/', so the cookie will be available for all pages:
setcookie($GLOBAL_COOKIE_KEY_CREATED_CV_THEME_ID, $param_themeId, time()+$GLOBAL_COOKIE_EXPIREDAYS, '/');
Ref: http://us.php.net/setcookie
Hope this could help, but if someone found it's wrong, please comment, thanks.