I agree with what Joe ( VanCleave ) and Don (blindpig) wrote in this thread about rendering nice skies on paper negatives -- whether using graded paper or VC paper. You can get very dramatic skies if you underexpose and leave the foreground as a silhouette. Here are two more ways to get skies on a paper negative:
1) overexpose and under-develop the negative. If you add 1.5 or 2 stops of exposure, you can develop by inspection in dilute developer. The overall effect is to reduce contrast, and with this method it is possible to retain cloud details in the sky. The darkest areas on the negative will not be black, but gray or brown-ish grey, but they still contact print nicely. I think I used dektol diluted with ice water... takes some patience because you don't start to see the image for a few minutes. A few examples are
here.
2) The other time I saw reduced contrast to the point that details in the sky remained visible was when playing with H2O2 reversal ( long thread about it
here ). The version of the process that uses re-exposure to light and redevelopment in paper developer likes to have the original a bit underexposed... I pushed that idea a little. An example
here.