first thing to check is that the server is properly saving the cart to a session. use the Session test page from the following post to check the session management on the server:
showpost.php?p=23826&postcount=2
if the session test fails, you will need to contact the host to have them correct the problem, most likely it is a bad session.save_path setting in the php.ini file.