Paul Irish has outlined the current state of @font-face. Here's a slideshow and a small gathering in Boston reviewing it all:
http://paulirish.com/squeeze/
http://www.ustream.tv/recorded/4828154
The quick answer is 95% of A+ browsers utilize it (FF 3.0 is the exception). Licensing can be tricky, but several tools are of aid, such as FontSquirrel, FontDeck, and FontSpring.
Probably the hardest part of implementation is dealing with Firefox which has a FOUT ("flash of unstyled text") on load, though there are several workarounds, including:
http://paulirish.com/2009/fighting-the-font-face-fout/
http://inspiringpixel.com/articles/web-design/fight-the-fout/240/
http://www.stevesouders.com/blog/2009/10/13/font-face-and-performance/