Attaching the image (limit 100K) would help us know more about what to advise -- it depends on how much other "stuff" is interwoven with your sky. If it's just a landscape with a gray sky and nothing jutting into the sky, you would just paint the sky area to create your selection and adjust it or replace it with another sky more to your liking.
If it is more involved (branches, buildings, people, etc. ), you may need to use another method of masking.
Here's a case in point from this site -- read through all the entries and see if it helps you decide about what you need to do with your image.
If you need help posting your image, just tell us and someone will help. The sizing works best if you use Save File for Web -- in Photoshop, that is. http://www.retouchpro.com/forums/sho...hlight=replace