So, here is the long annoying way to do this, which is not always entirely accurate. You put on your grid, and then rotate accordingly. This makes it look good to an average eye, but if you are in industry and need something so incredibly perfect, or you don't feel like changing your grid from the thirds (good for you, following those design rules) Below, I will teach you a much easier way that is 100% accurate with a tool you may have never seen.
______
So, you are the idiot who shot the photo on an angle. Such a beatiful shot too. We're going to straighten up the photo. Be for-warned that because you already screwed that up, you'll loose a little bit of area on the outsides in the end (or you can redraw it with the clone stamp tool like I enjoy doing)
Appearing in the picture below is the "measure tool" It is right behind the eyedropper tool. If you click and hold on the eyedropper, you will see a few other tools. The bottom one being, of course, the measure tool. This works just like the polygonal lasso tool in theory, though you click and hold instead of click twice)
______
What you want to do is use this tool by clicking on one side of the horizon, and let the line run to the other side of the horizon. Below is what your image should look like at this point.

_______
Now go under the "Image" drop down menu, go to "Rotate Canvas", and then "Arbitrary" Normally, you can enter how much you want to rotate in this tool. However, you used the measuring tool to preset the degree's of change it needs, so the numbers will be preset. Click ok.

________
Good, now your image is LEVEL!!!! However, you got that icky background everyone.

________
At this point, you can go one of two routes depending on how good you are with the clonse stamp tool. Later on, I'll cover tips with that, but for now, let's just crop in on it.
Before:

After:

All done! Nice picture by the way!