There doesn't seem to be an official Debian package yet (at least I couldn't find a natty ppa), so I installed from source with checkinstall.
Checkinstall (instead of make install) creates a local .deb package, which can be uninstalled via
dpkg -s vlc when the official repositories catch up.
The configure script kept popping up with missing packages, so I posted a list here.
It's probably not complete (depending on what I had installed already) and might include a few unnecessary dev packages. Anyway, missing packages can usually be resolved by
aptitude search <keyword>.
Checkinstall failed at first being unable to create /usr/local/include/vlc and not finding vlc-cache-gen
(
source).
Afterwards, vlc crashed at startup missing some libraries, which had ended up in
/usr/local/lib instead of
/usr/lib, so I had to create a few symbolic links (
source).