Open Synaptic (System -> Administration -> Synaptic Package Manager). In Settings -> Repositories, make sure you have a "multiverse" repository activated.
Search for vlc and install it. You should also install vlc-plugin-esd, mozilla-plugin-vlc (and libdvdcss2).
You need to check that a "multiverse" mirror is listed in your /etc/apt/sources.list.
% sudo apt-get update
Ubuntu Jaunty Jackalope 9.04,
The instructions for Ubuntu also apply to Kubuntu. But you should:
* Use Adept instead of Synaptic;
* Install vlc-plugin-arts instead of vlc-plugin-esd
Ubuntu Downloads Information