I've done a fair bit of pixel art on my Tungsten E Palm.   I've found that you generally still need to do a bit of cleanup and color adjustments after, but not a huge amount.

I use Moepaint for doing pixel art on the Palm, it's the best paint software I've found as well as being free!  The developer seems to have taken down the offical page for it but you can still find it here: http://www.pdaload.ru/modules.php?name=Downloads&d_op=vi ewdownloaddetails&lid=1091&ttitle=MoePaint&pid=p alm&newlang=english

It has layers, transparency, zoom (up to 800%) and can save and load bmp files off a memory card.

Here are a few pixel drawings I've done that were created mainly on the palm:


These characters were done in moepaint, and backgrounds added after in photoshop:




Hope that helps!