It would be difficult to talk about video playback without talking about the YouTube application. Apple is clearly working tightly with the video giant to integrate users' videos into their products. The YouTube application has a number of tabs for featured videos, most played videos, as well as your own bookmarks and selections. You can also search through the library of videos that have been re-encoded for playback on the iPhone (and Apple TV).
There are two versions of each video, one for streaming over the EDGE network, and another for streaming over Wi-Fi. The EDGE versions are blocky and choppy, much like the bulk of streaming video available for phones today, no matter what network they're streaming over. Playing these videos back on the iPhone's high resolution screen only amplifies their low quality. However the Wi-Fi version of each video is amazingly clear and smooth. So much so, in fact, that these look better than what you see played back on you PC.
It's difficult to estimate what percentage of YouTube videos can be accessed through the iPhone. Apple says over 10,000 were ready on launch day. That only includes two Phone Scoop videos, but it does include many entertaining clips including podcasts and commercials that you've been dying to show your friends.
The YouTube application lets you bookmark videos you want to save as well as email links to them.