It sounds like your web host doesn't have PHP sessions configured properly. You need to bring this to their attention and have them fix it. Who is your webhost, BTW?
There have been several posts on this forum about others who have had similar problems - a search on php sessions brings up a list of 30 different posts.