Just recently I acquired a new mobile phone, one running Android (in my case a HTC Magic) and I've had a quick look around for some astronomy software but didn't find much.
Then, this evening, I noticed this tweet from Stuart and went and did a little digging about and finally found it.
Rather that try and explain it, I'll just go with Google's video explaining it:
The one warning I would give is that it takes quite a while for the application to start. It will look like your phone has hung (and, if you try and do something, you'll probably be told the application is taking too long and would you like to force an exit or wait) but just wait a little, it's simply slow to start. Once it's running it's nice and snappy.
If you've got an Android phone and astronomy is this thing I'd call this a "must have" application — even if you do know your way around the sky.