Both Firefox and Opera already released WebM (VP8) capable nightly builds which you can download from here:
To run Opera in Ubuntu, download the archive, extract it and double click the "opera" file. Then try out this video which already uses WebM (with VP8) - but don't forget to enable HTML5 for YouTube before watching the video.
Ubuntu users: if you want a WebM capable Chromium, add the Chromium daily PPA - the latest builds (as of 20 May) already have WebM support. Install it with:
"chromium-codecs-ffmpeg-extra" is required by WebM it seems.
sudo add-apt-repository ppa:chromium-daily/ppa && sudo apt-get update
sudo apt-get install chromium-browser chromium-codecs-ffmpeg-extra
Note: Google Chrome (not Chromium) will be getting WebM support starting with May 24.