Just to reiterate, PNG is perfect (lossless) quality. However, many paint programs have very shitty compression algorithms (Photoshop in particular.) So, we like to use the utility pngcrush (http://pmt.sourceforge.net/pngcrush/
It works super good. It compresses every last little byte out of your PNG files (and still losslessly). We use it on the default skin to save about 180kbytes off the size.
We use the options "pngcrush -brute -reduce", which makes it try every possible variation in the compression schemes and write out the smallest one.
Another thing you can do to shrink PNG size is to save it out as grayscale (if that makes sense for your bitmap of course) or to reduce the colors down to 8-bit mode (if that looks ok). Now, those are lossy operations, but pngcrush will be able to compress them even better if you do that.