For all those folks who have had success getting their google account set up (link), the "Cloud Print Beta" app works like a charm.

You don't need to have the Android Market working, just the google account.