It depends on what you're making and how your image looks, but I would say, in general, probably earlier in the process.
For example, if there are a lot of clouds with sun peaking through them creating a lot of contrast, you might want to replace the sky earlier if you're planning on putting text there so that it's easier to read.
Or say that you're trying to create a particular mood or add interest, you could try different skies later in the process.