Hola,
En Premiere lo que creas primeramente son "Proyectos" que tienen extensión .pproj y no son videos en si, y por tanto no pueden ser reproducidos desde un reproductor normal. Lo encontraras en el menú Archivo > Exportar > Medios.
Primero debes exportarlos con el Media Encoder al formato que veas más apropiado como dice UserAlfa, que pueden ser ademas de mp4: swf, avi, mov, mpg... según el reproductor que vayas a utilizar. Si puedes elegir, prueba distintos para ver la calidad de salida y el tamaño que te ocupan.
Saludos!