Are you playing back in Quicktime or some other application?
In Quicktime they should view correctly but most other codex don't seem to support the orientation stored with the video [if not, and you have Quicktime Pro you can set the orientation].
In VLC you can manually turn on rotation through the menu and there is a command-line flag as well:
http://www.videolan.org/doc/play-howto/en/ch04.html
--transform-type {90,180,270,hflip,vflip} Select rotation angle or symmetry.
The "proper" orientation for the device to play by default is to hold the phone with the home button on your right (volume control buttons towards the floor). Unfortunately, it will not set level on a desk that way because of the buttons.
Camera = iPhone afterthought