It turned out it was fairly easy to do.
First, select your photo, in this case with the sea it was obvious that I wanted the sea bent, but the sky left. So I cropped the photo to give a thin-ish band of sea at the bottom of picture, in this case it was 400px of sea, before the sky cut in.
Then you need to add some guides. The key here, as you'll see later, is to have 8 horizontal guides as we're going to distort the picture. These need to be the same width apart as the bottom band, so again 400px in my example, to match the depth of the sea. I used the 'New Guide Layout' option in photoshop to place these for me, but if you have an older version of Photoshop you'll have to do the maths yourself. Set the guides up as shown below, replacing the width with the number of pixels you need.