Lo primero, revisar la compatibilidad de navegadores para mostrar videos:
http://www.w3schools.com/html/html5_video.asp
Luego, si vas a permitir que se suban los videos en cualquier formato, debes convertirlos a los soportados por navegadores y, ya entrados en gastos, también para dispositivos móviles, generalmente: webm, mp4, ogg y 3gp.
Finalmente, crear la etiqueta de video, con fallback para los diferentes navegadores, tal como el ejemplo del enlace.