Are you optimising them "by hand" with desktop software, such as Photoshop/Fireworks? Or, does your server resize and optimise images?

If you're using Photoshop/Fireworks, you just need to reduce the quality of the images sufficiently so that they're a small file size and still look decent. With Fireworks you can set a desired size for the resulting file in kilobytes, which can be quite handy.

If you're resizing images on the fly at the server side, you need to do the same kind of thing using a server-based application such as GD or ImageMagick. I prefer ImageMagick myself, and I've written some PHP code to get the maximum image width the device handles (from TeraWurfl) and then output an image of that size. There's a bit of overhead in doing this on the fly, so I cache all of the images produced. I doubt that it would be that much of an issue to do it without caching though, as at present mobile sites don't get vast amounts of traffic, compared to fixed-line ones.

Most mobiles handle jpg images well, so those are the ones I prefer to use. If you've uploaded PNG/TIF or other formats, you can easily get ImageMagick/GD to output the same image in JPG format.