I'm using Photoshop CS2, it should be pretty much the same in other version.
Open the photo. Create a new layer. Select the gradient tool (same button as the bucket-fill tool). On the top tool-bar, click on the gradient picker and choose the 'Foreground to Transparent' option. It's the second one on mine, it's got color on the top left and fades to the gray box pattern. Now select the color you want to use. Click on the top of the photo and hold, drag down to somewhere around the horizon line and leg to. Voila.
Personally, I think it looks more realistic if you switched the layer blending to 'Multiply.'
Origional photo:
Photo with colorcast sky:
Photo with colorcast (multiplied) sky:
