For extra savings, PNG usually compresses significantly better than GIF, though certain tools such as Adobe Photoshop have notoriously poor PNG compressors. I have found the best results (using photoshop) is to save the file as a GIF (Which lets you use Photoshop's dithering and palette selection tools) from Photoshop, and then use a tool such as gif2png to convert the GIF to a PNG file. There's no problem with a site using both GIF and PNG, so feel free to mix and match, using whatever format provides the best compression for the image in question.
If you must save directly to PNG, you can probably shrink the PNG further by using pngcrush. pngcrush attempts to recompress the PNG file using more effective compression settings.