There is a whole laundry list of things you need to do to avoid ending up in spam folders, but probebly the most straightforward advice is don't call mail(). If you're calling mail directly, it's almost guaranteed you're sending an incorrectly formatted message. Nearly all the example code you'll find will have mistakes in, and though it may well scrape through to some email servers, any that are paying attention (as they increasingly are) are likely to think you're a spammer.
So, before trying to fix anything manually, I suggest you grab one of the myriad PHP email libraries: PHPMailer (of which I'm a maintainer), SwiftMailer, Zend_Mail will all do a better job than your code.
After that, make sure your DNS resolves forwards and backwards, set up SPF and DKIM (DKIM is tricky, though PHPMailer supports it), register your domain for feedback loops from all the major hosts (hotmail, yahoo, aol etc, though some require 6 months notice!). It's unikely that your IPs are blacklisted on a hosted server (unless you've been sending lots of spam), but be very careful if you have dynamic IP or varying hosts (like EC2) as you may inherit someone else's spam problem, or get bundled in with a block of guilty IPs.
Check typical examples of your messages with Spamassassin to see if you're doing anything obviously spam-like - even if you don't think it's spam, SA is what is commonly used, so hard luck if it doesn't like your messages!
If you have a good enough mail server, make sure you do adaptive rate throttling to domains you send to a lot based on their deferral rates.
If all this sounds hard, it's because it is.