I just got an iPhone 4 and I'm trying to figure out how to get my contacts on it. I don't have an exchange account, which seems to be the only Google Sync option. Edit:move*
Open Address Book on your computer and go to Preferences > Accounts. Turn on Synchronise with Google and enter your Google account details. Your contacts will come through to Address Book and will then synch to your phone in iTunes.
I feel stupid. I didn't realize you can just do it in the drop down on the info tab when your iPhone is connected. Thanks for the help though.