Ubuntu Jaunty Jackalope 9.04,
Ubuntu Intrepid Ibex 8.10,
Ubuntu Hardy Heron LTS 8.04
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).
Command line way
You need to check that a "multiverse" mirror is listed in your /etc/apt/sources.list.
% sudo apt-get update
% sudo apt-get install vlc vlc-plugin-esd mozilla-plugin-vlc