Open a new Terminal window (Applications -> Accessories -> Terminal) and execute the following command:
sudo apt-get install vlc vlc-plugin-esd mozilla-plugin-vlc
This will install VLC media player along with the plugins. If you do not want to install any plugins, use the following command:
sudo apt-get install vlc
After installation is complete, you can run VLC media player by going to Applications -> Sound & Video -> VLC media player.