A WWW 2008 paper out of Google, "Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph" (PDF) presents "a novel method based on the analysis of the entire user-video graph to provide personalized video suggestions for users."
Not sure if the same technique was used, but YouTube recently launched ( ) recommendations.
Update: Ten days later, Googler Sapna Mehta announces video recommendations on Google Video.
These recommendations appear to be quite different than the YouTube recommendations, based on your Google web and search history rather than the YouTube videos you watch and almost certainly using different techniques under the covers.
Interesting to see Google making a push on video recommendations both on YouTube and Google Video.
Please see also a review of the new Google Video recommendation feature on Search Engine Land.