PHP can be installed in 2 different API modes: 1) as an Apache module 2) as a stand alone CGI. Your host is using the CGI mode. The Apache module is better in just about every respect as far as speed and ease of use but some seem to think it compromises security.
Anyway, since you are stuck with CGI PHP, you must treat you PHP scripts just as you would any other CGI script. You must put the path to the PHP executable and the top of your scripts (#!/usr/local/bin/php). There msut not be any space before this line. You must upload you scripts in ASCII mode and you must set the permissions on your scripts to 755 using CHMOD.
A note about the #!/usr/local/bin/php line: only scripts called directly by your browser should have this line, not scripts that are included or required by other scripts. That is to say if you have a file call "file1.php" that has the line:
<? include ('file2.php'); ?>
then only "file1.php" should have the path line, not "file2.php" (if you do put the path line in "file2.php" then it will be echoed back to the browser).
PHP CGI is a real pain, ask you host to switch the Apache module or at least tell them to check out mod_phpcgiwrap.