>What exactly do you have to pay to Google to "license" Android?

For one thing, all of Google's core applications - Gmail, Maps, Search, Google Voice, Googles, etc. Same thing with the Marketplace too. All the handset manufacturers have to pay Google to include those apps on their handsets.