http://tinypng.org/ is a great service, they optimized my png images by ~67%. How does their service work? How can they minimize size and quality of pictures still remains the same?
The answer's right on that web page:
When you upload a PNG (Portable Network Graphics) file, similar colours in your image are combined. This technique is called “quantisation”. Because the number of colours is reduced, 24-bit PNG files can be converted to much smaller 8-bit indexed colour images. All unnecessary metadata is stripped too. The result: tiny 8-bit PNG files with 100% support for transparency. Have your cake and eat it too!
It turns 24-bit RGB files into palettized 8-bit ones. You lose some color depth, but for small images it's often imperceptible.
You can do the same thing manually on the command line with this awesome tool: http://pngquant.org/