The simpliest way is to use the same technique you yourself described.
Make a new Image
Get the Graphics property of the Image
Draw the smaller images onto the Image using imagesGraphics.drawImage(...)
You now have a large image consisting of all your smaller ones
Then just draw the large Image to the screen using graphics.drawImage(...)