Cuando agregas un nuevo contacto, en la parte de arriba, antes de ponerle un nombre, sale una casilla donde indica el lugar donde se guardará. Si quieres que se guarde en gmail, tiene que estar puesto Contacto Google. Igual es que tienes puesto ahí Dispositivo o Sim.
Para sincronizar todos los contactos con Google, vete a Ajuste-Cuentas. Pincha en la cuenta de Google, y luego pincha en el nombre de tu correo. Finalmente pincha en Sincronizar Contactos.
Espero te sirva.