Whenever I see nighttime long exposures with the moon, the moon is always way overexposed. I understand it's a bright object, but why don't I ever see HDR done to compensate for that? Does it look unnatural?
This is done but most photos do not advertise their technique. If you search for moonscape on Google you will see lots of examples, mixed with some other artwork.
The most common technique to include the moon though is not HDR. It is double-exposure. Unless the moon intersects something else in the scene, there is no need to use HDR and risk blurring from blending images or camera movement.
Lots image images you see online or in calendars and post-cards which include the moon are made with double exposures. This allows a proper exposure for the moon and a separate one for the scene, plus you can place the moon wherever you want which may work better with the composition. This is not journalistic photography obviously but quite an old technique.
I've tried it and it doesn't work very well. In my case I was trying to get the moon through bare branches of a tree.
A correct exposure for the moon gives everything else completely black. A correct exposure for the sky (say 1 hour after sunset) showing the branches in silhouette means that the moon isn't just overexposed, it bleeds light onto surrounding pixels -- it's a serious light source compared to a dark sky.
In fact, the exposure for the tree branches (or other surroundings) can be long enough that the moon moves appreciably in the sky (and the branches move in the wind unless it's a completely still night). The time lag between exposures can also allow the moon to move, as auto HDR typically won't stretch far enough so you have to do manual settings (including ISO) which takes time.
You might get it to work with the moon in a clear area of sky, but essentially you'd be doing a double exposure rather than what's normally considered HDR (see @Itai's +1 answer for more on double exposures), just without moving the camera.