Set Default Video Player – How to Change Default Settings

There's yet another GUI solution, which might come handy for you ;)

Try opening the properties (right click -> Properties) of the file type you want to be always played by VLC.

Choose the Open with tab and either choose from a list or add one (by choosing from an extended program list or simply typing vlc as the command)

EDIT:

... and click on Set as default

Go to System Settings → System info → Default Applications, and set it there. It works in Ubuntu 11.10 (Oneiric Ocelot).

In Ubuntu 13.04 (Raring Ringtail) and later, it's found in System Settings → Details → Default Applications.