Pues suponiendo que uses Gnome: Aplicaciones -> Primera opción -> Terminal o algo así. Luego en la terminal escribes el nombre del programa que sea, que supongo que será totem o vlc, y le das a intro. Puedes usar tabulador para el autocompletado en la terminal y para ver las opciones que tienes.