commonsExplorer is an experimental interactive browser for the Flickr Commons, a collection of pictures with "no known copyright restrictions." It provides a "big picture" of these collections with a single screen interface that reveals structures and patterns and encourages exploration.
commonsExplorer is a Java executable, so Windows and Linux users will need to have Java installed. The application requires a network connection, and may not work from behind a firewall or proxy.
Creative Commons has had its own search function for awhile according to a post at Google Operating System, which has a nice cache of articles on new features in Google Image search, which can filter for usage rights under advanced search.
For video, see Free Online Stock Video Footage | 9 Of The Best Public Domain Video Resources from WebTV Wire (one dropped out); for audio see Videomaker's compilation of royalty free sound FX and Legal Music For Videos from Creative Commons.
Update: via @juanmiguelsalas comes 15 Best Places for Designers to Get Free Stock Photos Online by Six Revisions.
Update 2: see Royalty Free Music For YouTube Videos at Who Is Matt, and Openfootage.net.