Not necessarily, there is one other potential cause non-related to cookies.
Are you sure you are using cookies for your sessions? Are you passing a querystring in any fashion that would allow the second domain (this is a domain right? Not a subdomain which is a completely different problem) which if hosted on the same server could read the same session file?
The only time websitea.com and websiteb.com can actually change data in each other's sessions is if they are on the same server AND phpsessid is passed through the querystring to the other server. You can try changing the save path locally by setting session_save_path to a new location prior to calling session_start.