Here's a quick easy way that takes seconds and works perfectly (note this is Photo shop CS3 Beta, but the technique is the same for older versions)
First of all, take your crooked horizonal photo:

select the Ruler tool and draw a line from one side too the other following the horizon in the picture:

once you have the line, select from the image menu, rotate canvas, and arbitrary:

Photo shop will instantly calculate the required rotation perfectly to get the horizon line dead straight, so press ok and it'll look like this:

Then simply crop the edges off and viola, one straight horizon:

it takes all of about 10 seconds when you get the hang of it
pretty neat huh?
Cheers,
Matt