Como poner letras a un video?

Hola familia, llevo un tiempecillo en esto del video pero en plan simple y con poca dedicacion. me gustaria saber como puedo poner letras a un video que ya tengo, tipo karaoke pero en plan wapo. Con que programa se hace? After Effects? Premiere? Algo mas simple ? Un saludo

el propio premier tiene la opcion de insertar texto, yo personalmente he utilizado algunas veces el flash, volcando el video a avi, cargandolo al flash y currandome ahi las movidas.