There are three main things to consider when doing this type of low resolution/retro pixel artwork:
Determine what your game's available palette will be. We're not talking art direction yet, but total available colors.
Check out this Wikipedia article on game console palettes for reference.
As you can see in the article, Original Game Boy has a very limited 2-bit palette (4 shades of black!), while Game Boy Advance has a larger 15-bit palette.
Try to select a palette that will make sense with the resolution you choose:
Resolution in this context means the screen's pixel dimensions, or your game's target simulated pixel dimensions.
Here is a small list of assorted common resolutions. You can see that DOS and SNES games offered very few pixels for detail.
Once you have decided on these things, the rest is up to your artistic expression. Open up a new raster document in the image editor of your choosing, set the dimensions to your desired resolution, arrange your usable palette, and start drawing! :) Make sure to stay in 72dpi when using Photoshop.
I'm not familiar enough with Android development to know specifics, but you need to find a way to display your graphics using a specific scaling algorithm so that they will fill the screen without bleeding and anti-aliasing, messing up your nice pixel art work. In Photoshop, this scaling algorithm is called "nearest neighbor." Look up "nearest neighbor scaling" for Android and see what you can find.
Furthermore, Android devices vary drastically, so cheat a little and add some bleed detail on your images so things don't get cropped.
Make sure to check out some pixel art tutorials, especially on dithering. Good luck!