Graphical way

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-pulse, mozilla-plugin-vlc (and libdvdcss2).

If you are interrested in streaming or transcoding, you should also install libavcodec-extra-52.
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-pulse mozilla-plugin-vlc