Google Sync already works on BlackBerry. For the rest of the mobile phones, you can only synchronize contacts if there's support for SyncML. Contact synchronization should work on some Nokia and Sony Ericsson phones, for example Nokia N-Series and Sony Ericsson W-Series.
Before synchronizing data, read the known limitations of the initial release and follow the instructions from Google's site.
Google mentions that the service available for iPhone and Windows Mobile uses the Microsoft Exchange ActiveSync protocol. "When setting up a new Exchange ActiveSync account on your phone, all existing Contacts and Calendar events may be removed. Please make sure to back up any important data before you set up Google Sync."