There are numerous ways that can be done. Maybe you could post your picture here in the forums so that somebody could give you a recommendation for your particular image?
Depends how you want to change it. Some common methods:
Maybe I should have been more specific. I want to learn how to replace the sky in a photo. I have the newest version of photoshop and all the tutorials are several years old and don't work with this version.