YouTube uses the Flash Video Format (flv) and a Flash Video Player for their videos. The short story is you have to download the video to the computer, convert it to a supported by the Zune Software format and sync it to Zune. We use eRightSoft's SUPER video converter to do this. 

EDIT1: "SUPER" now supports Zune (wmv8 & wma2) since the build 21 version. So most of the problems on users comments, are solved now.

EDIT2: For IE there is a new plugin which compresses the following tutorial to only one click! Highly recommended. Check ZuneMyTube .

There are also other ways to do it, but one easy is with Firefox using the VideoDownloader plugin. After installing it, you can see at the bottom bar of Firefox a small icon. (It is where the arrow points)

This is a video from the past, Bruce Dickinson's "The Tower". So by clicking the VideoDownloader's icon while on YouTube, the following window opens:

Then click "Download Link". Depending on your preferences a dialog asking you where to save the file may appear. Then go to the file and change its name to something.flv . Zune Software cannot handle Flash Video files, so we need a transcoder. We use eRightSoft SUPER (its free) but you may use any flv to Zune (wmv, wma) or to iPod converter. Right click somewhere on the program and on the menu that appears click  "Add Multimedia Files" and select your flv video. You can use the following settings:

Next right click again on the program and select the place you want your video to be saved. (Otherwise SUPER saves it in "c:\Program Files" under the program's folder). After this, click "Encode" and wait... In some minutes your video will be ready to add on Zune's library and sync to the Zune.

 Almost tha same applies to Google Video service. I didn't add a red arrow to the plugin's icon here because the new Bond's girl is enough!

When you click the VideoDownloader icon you get a bit different menu than the one on YouTube:

Here there are 3 options: Flash Video (flv), avi (mpeg4) and iPod's mp4 (also mpeg4). I suggest you download the avi (or the mp4). In any case you need a converter again (mp4 is supported by Zune's Software, but not for  this codec). eRightSoft is a solution:

From here you do the same as for YoutTube and here is the result:

If you have any difficulties feel free to ask in our user Forum.