Many moons ago, we ditched the default blue blob header on this wordpress blog. It took us a while to figure it out, but once we did it, we thought we couldn't forget. Well, we did forget. I finally figured it out again today. Here's how it's done -- because I'll probably forget again in a few months.
First, Owen Winkler's Kubrickr tool makes a large part of this process really easy. Following the directions on his site, just search for and select the creative commons image of your choice. Crop it and save it to your desktop. The image is already properly named. Do not rename it! (Also, make a note to mention the photographer somewhere in your site.)
Now FTP the image (it should always be named kubrickheader.jpg) to your site/www/wp-content/themes/[choose the current theme you are using - not necessarily the default theme!]/images/
Now overwrite kubrickheader.jpg with the new image from your desktop. Upload, refresh, ta-da!
My fall 2008 header image is compliments of flickr's .bean.