Firstly, you need to write here model of your phone and firmware version.
Some examples from practice.
LG Optimus One. I didn't realize very long time how to make Google Contacts from phone. It is simple. When you create contact there is on top of windows drop-down box, where are three items:
Google. It is obvious where each item saves contact data. Default item is
Phone. Video how to create contact and select it's type.
HTC Inspire 4G. Default behavior is to create Google contacts. But there is also drop-down menu where I can select
Please look through your phone menus more thoroughly.
Also you can make contacts directly in web-interface of GMail. After small time they will be available in phone. And when you edit such contacts, they are edited on Google server too. One thing you need to make such functionality available is to connect your phone and your Google account.