Resizing, Cropping, & changing background
 

Sorry about that. I should have explained.

To resize the image go to Image then canvas size, I gave it 2 centimetres in height and width, this gave a white border all the way round. Then I re-cropped the image to centralise it.

I then used the magic wand to pick the border. Rather than use a bucket fill which would leave a flat border, I used the clone tool to clone the sky into the new border. Deselect the area and then use the patch tool to tidy things up.

To change the sky colour I used the magic wand to get the sky, it was set for 5 pixels so I didn't take any of the plane.
I then used the Gradient tool with the foreground darker than the background. Place a line from the top to the bottom of the image this gives a good graduation of the two colours.
Finishe.

Select the sky with the magic wand with tolerance set to about 5. Then clean up the edges of the plane with the lasso tool.

Select the colour of blue of your choice as the foreground colour, with white as the background, then filter >render > clouds

Then make a rough selection towards the outside of the image, feather the selection (I chose 25 px but that depends on the sise of your image) then use levels to darken the edges of the image :D

Here is a B&W version.

I did try some cloud effects but I prefere this.

Thanks Gidders.
That's a good explanation on how to create your own sky out of two layers, its a method I will have to have a go at. I couldn't find a decent photo of a sky to use.