What media formats are playable/streamable on Apple TV? For both the new (tiny) generation, and the last generation, what media formats and codecs are supported for streaming to Apple TV?

How does that streaming work -- is it all iTunes-based, or are there other ways to go about doing it?
The original Apple TV (out of box) preferred to treat your Apple TV like an iPod. It wanted you to sync your video from iTunes and had the following limitation:

H.264 and protected H.264 (from iTunes Store): Up to 5 Mbps, Progressive Main Profile (CAVLC) with AAC-LC audio up to 160 Kbps (maximum resolution: 1280 by 720 pixels at 24 fps, 960 by 540 pixels at 30 fps) in .m4v, .mp4, and .mov file formats
iTunes Store purchased video: 320 by 240 pixels, 640 by 480 pixels, 720 by 480 pixels (anamorphic), or high-definition 720p
MPEG-4: Up to 3 Mbps, Simple Profile with AAC-LC audio up to 160 Kbps (maximum resolution: 720 by 432 pixels at 30 fps) in .m4v, .mp4, and .mov file formats

The new Apple TV has identical requirements as that of the new iPod touch and iPhone 4:

H.264 video up to 720p, 30 frames per second, Main Profile level 3.1 with AAC-LC audio up to 160 Kbps per channel, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats
MPEG-4 video, up to 2.5 Mbps, 640 by 480 pixels, 30 frames per second, Simple Profile with AAC-LC audio up to 160 Kbps, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats
Motion JPEG (M-JPEG) up to 35 Mbps, 1280 by 720 pixels, 30 frames per second, audio in ulaw, PCM stereo audio in .avi file format

As for how it works, while nothing hard has been released from the UI screenshots released items from the internet (iTunes store, YouTube, Netflix, etc.) will stream from their respective sources while your photos, music and video streams directly from iTunes or from an iPhone, iPad or iPod touch (via AirPlay coming in iOS 4.2)