Die Seite erklärt das doch ganz schnuckelig.
Erst besuchst du mal die Seite hier: http://easyurpmi.zarb.org/
Die hilft dir, die benötigten Paketquellen hinzuzufügen.
Dort gibst du deine Mandriva Version an, die benutzte Architektur (i586 wenn du es als 32Bit-Version hast, oder x86-64 bei 64Bit. Bei Unsicherheit, tippe 'uname -m' in einem Terminal) und deinen Paketmanager, das wird höchstwahrscheinlich urpmi sein.
In Schritt 2 wählst du aus, welche Quellen du willst, für vlc brauchst du contrib und plf.
Danach bekommst du ein paar Kommandozeilenbefehle vorgesetzt, die du wie beschrieben in einem Terminal als root eingibst.
Wenn du damit fertig bist, gibst du nur noch den auf der vlc-Seite erwähnten Befehl ein (ebenfalls als root), und fertig.

Als Videoplayer kann ich übrigens mplayer nur wärmstens empfehlen, mit dem sich so ziemlich alles anstellen lässt (ein wenig Beschäftigung mit der manpage vorausgesetzt).
Entweder er ist bereits installiert, oder du kannst ihn einfach hinzufügen, über das Mandriva Control Center und rpmdrake.