If the sky was cloudy, I would expect it to come out completely white on a print where the foreground is properly exposed because the difference in brightness is huge. If you want cloud detail and foreground detail, you need to burn-in the sky under the enlarger - just one tiny example of why people do their own printing instead of handing it off to a lab.
Originally Posted by mporter012
If you have a day of blue sky maybe with the occasional cloud, try a circular polariser or red-25 filter to darken the sky. Or at least an orange filter if you want to be a little more subtle.