Relativamente fácil
Código PHP:
$query = 'SELECT campos_que_te_interesen FROM tabla ORDER BY campo asc';
Dónde tienes que especificar los campos que te interesan recuperar, la tabla y el campo por el que lo vas a ordenar (ascendentemente o descendientemente).
Luego haces las comprobaciones pertinentes para saber si ha habido errores, si ha devuelto algún resultado etc...
Y luego un bucle que lo muestre. Si lo quieres hacer con un número de columnas especifico tendrás que llevar la cuenta de los elementos por fila en una variable, y cuando llegue al número determinado le metes un salto de línea (o una nueva fila de la tabla, o algo por CSS) y reinicias el contador.
y ya está, en cada iteración del bucle tendrás que mostrar la imagen y el link a la otra página que muestre el vídeo (pasándole como parámetro el identificador único del vídeo).
Más o menos se entiende por donde van los tiros, si tienes alguna duda más concreta, planteala.