I used to do this by using the ruler tool along the horizon or something that should be straight, then clicking Image/Image Rotation/Arbitrary. This would straighten the image, but then you would have to crop the image to get rid of the empty areas created by the rotation.
An easier way in Photoshop CS5+ is to use the ruler tool along the horizon, then click Straighten on the top bar. Voila! All done with one click!