On the WaxJelly blog today, there's a new tutorial showing how to combine PHP and the YouTube API interface to grab the information and a thumbnail of videos matching your search.
For the purposes of this tutorial, you'll only need to change one variable to actually see the script in action. If you don't have a youtube API developer ID, you can get one for free here. Other than that, this is a primative script that grabs the info, styles it into manageable chunks, and displays the first 4 pages of results.
First, they set up the values they're defaulting to in the script (GET vars). The call to the REST API is next, passing along the method, developer ID, page, number to show per page, and the tag to search on. The results of this are pulled in with teh file_get_contents and parsed with SimpleXML and looped through, combined with HTML, and outputted into a page looking something like this.