You can use an app like this one to export the contacts to a card format. Then import those contacts to the other phone. If the new phone is an iPhone you can just email the vcard file to the new phone then open it to import.
You can also export to vcard from the OS X Address Book in File/Export menu.