There have been a lot of people talking about how great the new Apple iCloud is going to be, and whilst I agree that it will be useful, it is nothing new. Also, if you have an older phone (like me) you wont be able to benefit from it as apple are no longer getting iOS updates.
I use Google Apps which provides me with the mail, contacts and calendar syncing. I have to say it is an excellent service considering its free. Once you have activated mobile support in the Google Apps admin, its a simple configuration exercise to get everything synced over the air.
Connect your phone to Google using exchange as the protocol. You can get more info on how to do this by going to http://m.google.com/. When you have entered your details, select what you want to sync out of Mail, Calendar and Contacts. (I sync all three)
You now have your phone set up (and backing up contacts) to the cloud. Now to get those contacts into your mac. Simples. Go to address book preferences, and select accounts.
Tick the box next to Synchronize with Google and click on the configure button.
Thats it. You can then head on over to iCal to get your calendar synchronised too.