The contacts should be saved as Gmail contact, with G icon next to it. Only then they are part of sync right now, they are stored directly on the phone.
Export all the contacts to your SD card. Once all exported, delete all the contact from the phone. Copy the contact file to your computer and open your gmail, import that contacts to your gmail. Then make sure the sync is enabled and the contacts will soon be sync with the phone.
Next time your save a new contact, make sure you choose GMAIL in your contact option.