How can a Java program running in the background properly clean up when the system is shut down?

If your program is a long-lived system daemon, you may want to write startup and shutdown scripts to start it at boot and stop it at shutdown. Most Linux distributions use the System V init mechanism - you can write your own and install it with the other scripts (in the /etc/rc.d tree, in the case of Red Hat).

Without a shutdown script, all you get is a SIGTERM from the system when it's quitting time. JVMs prior to 1.3 will respond by unceremoniously terminating, but 1.3 gives you the option to install a shutdown hook (Runtime.addShutdownHook()) that can handle your shutdown requirements.