You need to encode the image data into the format that has the right characteristics for your image. If it's 24-bit color and has a lot of colors and you want to lose no quality, you are probably stuck with PNG, but look into lossless JPEG 2000.
If you can lose some quality, then try
- Lossy JPEG 2000 -- much smaller than JPEG for the same quality loss
- reducing the number of colors and using a color mapped format
If the image has only gray or black and white data, make sure that you are encoding it as such (8-bit gray or 1-bit black and white). Then, make sure you use an encoder that is tuned for that kind of format (for example TIFF with Group 4 or JBIG2).
Another good option is to remove all of the unwanted meta-data from the image (or make sure that your encoder doesn't put any in).
If you want to stick with what's in Java, you probably have to use TIFF, PNG or JPEG -- there are third party image endcoders (for example, my company, Atalasoft, makes a .NET version of these advanced encoders -- there are Java vendors out there as well)
FYI: reducing bit depth usually means reducing quality (unless the reduction is meaningless). For example if I have a 24-bit color image, but all of the colors are gray (where R==G==B), then reducing to 8-bit gray does not lose quality. This is also true if your image has any collection of 256 different colors and you switch to a color mapped (indexed or paletted) format. You reduce the number of bytes and don't reduce quality.