Puedes añadir etiquetas a un vídeo al momento de subirlo y cuando quieras. En el segundo caso entra en la sección "Mis vídeos" de tu cuenta:
http://www.youtube.com/my_videosBusca el vídeo que quieres etiquetar y dale a "Editar", ahí encontrarás la casilla "Etiquetas". Las etiquetas tienen que ser palabras relacionadas con el vídeo separadas por espacios. Cuantas más palabras más posibilidades hay de que la gente lo encuentre en la búsqueda.
Tampoco hay que olvidar que el buscador tarda más o menos 24h en indexar vídeos nuevos.
