Here's a simple step-by-step guide for Gentoo users to start testing the newly released UVD support in the open source Radeon driver:

1. Buy something from AMD/ATI. Be a good open source citizen and vote with your wallet! Some good candidates include this and this.
2. Feel good about yourself.
3. Wait several years for AMD developers and lawyers to get their collective shit together. Use the shitty proprietary Catalyst driver in the meantime.
4. emerge --sync.
5. Say goodbye to x11-drivers/ati-drivers, replacing it with x11-drivers/xf86-video-ati. Make sure it says "radeon" instead of "fglrx" in the VIDEO_CARDS flag.
6. Install media-libs/mesa-9.2_pre20130404 and x11-drivers/radeon-ucode-20130402 kindly and promptly prepared by chithanh. All hail chithanh.
7. Grab the latest kernel source from the drm-fixes-3.9 branch. This tarball should work.
8. Apply all 11 patches from patchset v2 posted in the mailing list. Alternatively, apply this rolled-up patch.
9. Build kernel. Make sure to set CONFIG_DRM_RADEON and add the relevant firmwares to CONFIG_EXTRA_FIRMWARE (e.g. "radeon/PALM_me.bin radeon/PALM_pfp.bin radeon/SUMO_rlc.bin radeon/SUMO_uvd.bin" for E-350).
10. Add "vdpau" to the USE flags and recompile packages that make use of it.
11. Reboot. Join forums / IRC / mailing lists for group hug.

UPDATE: Patchset v3 is out in the mailing list. Essentially the same as v2, with one change moved from 02 to 03.