I have a cell phone. In the past-- I've broken my phone, lost it, or it has been stolen. I don't even bother keeping contacts in my phone anymore. If I want to call someone, I have their number memorized (believe me, I've been able to remember a lot of them), but it's very very inconvenient.

Gmail has the capability to store people numbers, addresses, email, etc, so that is where I store all my contact information just in case I happen to forget a number (which doesn't usually happen ever) but what would be really nice is being able to synchronize my cell phone contacts with my gmail contacts.

How feasible is this? What are different ways of Google going about making this possible/make it "Googley" and not just a random attempt at controlling all mobile devices?

They could add this feature in the Java mobile client.