Gallery of videos

maybe look at the Views module and then look at theming your View. That would be what I would do.

The best way to do this is to use Views + Views Bonus Pack (the bonus part you're looking for is "grid view"). When you make your view I suggest using thumbnails, as displaying multiple videos on the same page can create problems, and if you're using a taxonomy, then you can either filter for the one you want (obviously you should filter for nodes that have embedded videos), or use arguments if you know how. Also, if you use the dev version of the module you can also use thumbnails + thickbox, which gives you a nice little popup screen with the full size video when you click on the thumbnail (see here for an example: http://zivtech.com/videos)