Google Sky for Android - a map of the heavens
This has to be the coolest Android App - http://www.google.com/mobile/skymap/ (and it's free).
Point your phone at a star or planet and your Android lets you know what star or planet you are looking at.
Enter a star, planet or constellation name and your phone will guide you to it.
There's even a time travel mode for seeing where the planets were on a particular date/time in the past or future.
The geek factor on this app is off the charts, download it (search "Google Sky Map" from the app store) and have fun.