After spending a while trying to create paletted PNG files with transparency that work in Internet Explorer (after much trying, I couldn't coax ImageMagick to create such a file, though I was able to use GIMP to do it), I decided that GIFs were the only practical file format to be used. But it's hard to get a Java program to output GIF files.
Because of the whole patent licensing issue, there aren't really any good, full-featured, unencumbered GIF exporters for Java. But there are various good bits and pieces on the 'net, which can be pieced together to make something reasonable.
First, you need some code that can actually encode the GIF file. The US government has some code that can do this (offered as part of NIH's ImageJ). All you have to do is download ImageJ and grab their ij.io.GifEncoder class.
The ImageJ code only accepts paletted data as input though. Since most images are in 24-bit colour, you need to perform a colour reduction somehow. Fortunately, someone went and took the colour quantizer used in ImageMagick and rewrote it for use in Java. It uses an octree for its colour quantization, which is a technique described in much detail elsewhere on the Internet. The quantization code needs to be reworked a bit to properly handle transparent pixels, but fixing that isn't too much work. A more important fix though is that the code performs an unnecessary optimization to save memory, which results in poor quality quantization. In the constructor for Cube, it sets the tree depth to log_4 of max_colors. Instead, the tree depth should just be set to the maximum depth of 8. Although the original ImageMagick did limit the tree depth to log_4 of max_colors, they used another optimization elsewhere in the code to reduce the effect of that limitation.
Once you combine these two pieces of code together (you have to change some of the APIs to handle transparency and other things), then you end up with a very reasonable GIF exporter.