It depends on how overexposed it is. If it's really completely white and featureless, then there might not be anything to do, short of ElendilTheTall's suggestion of Photoshoping a new sky altogether.
But, assuming you have the RAW files and a RAW processor, I would first try to bring out some detail in the clouds. At the very least, make them a little darker while keeping detail in the rest of the photo. A quick outline how to do that:
Decrease the exposure of the whole image a bit.
Add some "Clarity" to increase the local contrast in the clouds.
Decrease the exposure of the highlights.
Increase the exposure of the shadows.
As with anything, adjust to your own liking. If the non-sky part of the image is also bright, you may need to use local adjustments to limit the above changes to just the sky.