To answer your immediate question: You don't execute a .exe file in Linux. This is for Windows. This binary has been compiled from source code into a .exe using Windows conventions and libraries. This is in much the same way a .dmg file runs natively on OSX, and so on.
The error message you gave is something you could very easily have googled, and so I would suggest you try that first next time, you'll solve your own issues then, and a lot quicker. Basically the error is saying that the computer has no defined way of opening a .exe file.
'Repeated Research', of course, failing to tell you the above, even though a google search
http://www.google.co.uk/search?clien...utf-8&oe=utf-8 provides over 9.3 Million results.
Installing VLC on Linux, what I would have expected to feature in your 'Repeated Research', provides fewer results; only about a million:
http://www.google.co.uk/search?hl=en...qi=g1&aql=&oq=.
Since you're showing up here as using Ubuntu, I would listen to repo and troop. If not, please use your distro's package manager.