Debian Jessie
Packages: xserver-xorg-video-ati, xserver-xorg-video-radeon, firmware-linux, firmware-linux-nonfree

I also ran:

sudo dpkg --add-architecture i386
sudo apt-get update
sudo apt-get install libgl1-mesa-dri:i386

Upgrading to fglrx-driver fixes problem.

Console Output:
dylan@Dylan-PC:~$ steam
Running Steam on debian 64-bit
STEAM_RUNTIME is enabled automatically
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
libGL error: dlopen /usr/lib/i386-linux-gnu/dri/r600_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: version GCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/r600_dri.so)) libGL error: dlopen ${ORIGIN}/dri/r600_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: versionGCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/r600_dri.so))
libGL error: dlopen /usr/lib/dri/r600_dri.so failed (/usr/lib/dri/r600_dri.so: cannot open shared object file: No such file or directory)
libGL error: unable to load driver: r600_dri.so
libGL error: driver pointer missing
libGL error: failed to load driver: r600
libGL error: dlopen /usr/lib/i386-linux-gnu/dri/swrast_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: version GCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/swrast_dri.so)) libGL error: dlopen ${ORIGIN}/dri/swrast_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: versionGCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/swrast_dri.so))
libGL error: dlopen /usr/lib/dri/swrast_dri.so failed (/usr/lib/dri/swrast_dri.so: cannot open shared object file: No such file or directory)
libGL error: unable to load driver: swrast_dri.so
libGL error: failed to load driver: swrast
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
Fontconfig error: "/etc/fonts/conf.d/10-scale-bitmap-fonts.conf", line 70: non-double matrix element
Fontconfig error: "/etc/fonts/conf.d/10-scale-bitmap-fonts.conf", line 70: non-double matrix element
Fontconfig warning: "/etc/fonts/conf.d/10-scale-bitmap-fonts.conf", line 78: saw unknown, expected number
libGL error: dlopen /usr/lib/i386-linux-gnu/dri/r600_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: version GCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/r600_dri.so)) libGL error: dlopen ${ORIGIN}/dri/r600_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: versionGCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/r600_dri.so))
libGL error: dlopen /usr/lib/dri/r600_dri.so failed (/usr/lib/dri/r600_dri.so: cannot open shared object file: No such file or directory)
libGL error: unable to load driver: r600_dri.so
libGL error: driver pointer missing
libGL error: failed to load driver: r600
[0702/063419:WARNING:proxy_service.cc(958)] PAC support disabled because there is no system implementation
libGL error: dlopen /usr/lib/i386-linux-gnu/dri/swrast_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: version GCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/swrast_dri.so)) libGL error: dlopen ${ORIGIN}/dri/swrast_dri.so failed (/home/dylan/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1: versionGCC_4.7.0' not found (required by /usr/lib/i386-linux-gnu/dri/swrast_dri.so))
libGL error: dlopen /usr/lib/dri/swrast_dri.so failed (/usr/lib/dri/swrast_dri.so: cannot open shared object file: No such file or directory)
libGL error: unable to load driver: swrast_dri.so
libGL error: failed to load driver: swrast
Error: OpenGL GLX context is not using direct rendering, which may cause performance problems.

For more information visit https://support.steampowered.com/kb_article.php?ref=9938-EYZB-7457.
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
[HTTP Remote Control] HTTP server listening on port 48910.
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
PulseAudio connect failed (used only for Mic Volume Control) with error: Access denied
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
Installing breakpad exception handler for appid(steam)/version(1401381906_client)
Generating new string page texture 12: 48x256, total string texture memory is 49.15 KB
Generating new string page texture 13: 256x256, total string texture memory is 311.30 KB
Generating new string page texture 14: 128x256, total string texture memory is 442.37 KB
Generating new string page texture 15: 384x256, total string texture memory is 835.58 KB
[2014-07-02 06:34:19] Startup - updater built May 29 2014 09:19:23
[2014-07-02 06:34:19] Verifying installation...
[2014-07-02 06:34:19] Verification complete
[2014-07-02 06:34:31] Shutdown
dylan@Dylan-PC:~$