Here's a tip to save all you new PS3 owners more than a few minutes of confusion. Even if you go out and buy the HDMI cable (not included) to use on your PS3, you'll still have to use the composite AV cable to set up your console first. Make sure to set your video inputs on your TV to display the video source that the composite cables are plugged into when it boots.
After you get into the menus, you can go into system display settings and change the display to HDMI, then switch over to Video 8 (or whatever your TV is) to display 1080p/1080i/720p.
Update: It may just be our TV. We'll look into it some more.