Довольно рутинная операция. Есть несколько способов.
Возьмём исходное изображение:

1. Самый простой.

Первый на stackoverflow.
Суть метода очень проста - создаем BufferedImage меньшего размера, затем прорисовываем в него исходное изображение.
Далее сохраняем обычным ImageIO.write()

        BufferedImage scaled = new BufferedImage(scaledWidth, scaledHeight,
                BufferedImage.TYPE_INT_RGB);
        Graphics2D g = scaled.createGraphics();
        g.drawImage(originalImage, 0, 0, scaledWidth, scaledHeight, null);
        g.dispose();
 
        ImageIO.write(scaled, "JPEG", new File("1.jpg"));

Результат:

Недостатки:
- Алгоритм сжатия хоть и быстрый, но результат неприятный.
- Реализация сохранения JPEG ImageIO по-умолчанию не радует.

2. Улучшаем качество JPEG-картинки.

Для этого делаем так:

   /* код приведён только в учебных целях! не использовать в продакшн */
   public static void saveAsJPEG(BufferedImage scaledImage, OutputStream out) throws IOException {
 
        ImageTypeSpecifier type = ImageTypeSpecifier.createFromRenderedImage(scaledImage);
        Iterator iter = ImageIO.getImageWriters(type, "JPEG");
        // берем первый попавшийся для JPEG
        ImageWriter writer = (ImageWriter) iter.next();
        ImageOutputStream ios = ImageIO.createImageOutputStream(out);
        writer.setOutput(ios);
 
        JPEGImageWriteParam iwparam = new JPEGImageWriteParam(Locale.getDefault());
        iwparam.setCompressionMode(JPEGImageWriteParam.MODE_EXPLICIT);
        // Вот здесь выкручиваем качество на максимум!
        iwparam.setCompressionQuality(1.0F);
        IIOImage iioimage = new IIOImage(scaledImage, null, null);
        writer.write(null, iioimage, iwparam);
        ios.flush();
        writer.dispose();
        ios.close();
    }

Результат:

Недостатки:
- Сильно вырастает размер файла. Это известный баг. Подробности здесь: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5028259.
- Алгоритм уменьшения картинки всё равно оставляет желать лучшего.

3. Используем хинты.

У Graphics2D есть так называемые RenderingHints, которые позволяют улучшить качество относительно настроек по умолчанию:

g.setRenderingHint(RenderingHints.KEY_INTERPOLATION,
RenderingHints.VALUE_INTERPOLATION_BICUBIC);
g.setRenderingHint(RenderingHints.KEY_RENDERING,
RenderingHints.VALUE_RENDER_QUALITY);

Результат:

Недостатки:
Качество стало лучше, но не сильно.

4. Уменьшаем постепенно.

Суть алгоритма - сжимать не сразу, а в несколько итераций.
Код можно посмотреть здесь: http://today.java.net/pub/a/today/2007/04/03/perils-of-image-getscaledinstance.html (очень позновательная и интересная статья, подробно расписано про уменьшение размера картинок).

Результат:

5. Метод из JDK 1.1.

Впринципе также можно воспользоваться методом из JDK 1.1:
Image.getScaledInstance(width,height, Image.SCALE_SMOOTH)

Image scaled = originalImage.getScaledInstance(scaledWidth,
                scaledHeight, Image.SCALE_SMOOTH);
g.drawImage(scaled, 0, 0, null);
g.dispose();

Результат:

Недостатки:
Реализация метода может различаться на конкретных платформах.