This seemed simple at first but wasn’t very obvious when I tried using iTunes. I had iCloud enabled which meant that I was not able to sync my iPhone contacts with my Mac Address Book. So, I switched off Contacts in the iCloud settings on the phone. Next I connected the iPhone, and via itunes, hit on Sync Contacts. This brought all the contacts into the Address Book.
Next, I exported all the contacts as a vCard file.
Then, logged into Gmail, and selected the ‘Contacts’ section. Used the import feature, supplied the file path, and saw that all contacts appeared.
Since I upgraded to an HTC Titan Windows Mango phone, logging into Gmail on it and syncing, automagically brought in all the contacts from Gmail into the new phone. And I was all set.
Took some time before I could figure all this out. iTunes+iCloud is not very straightforward when it comes to simple things.