From what I've seen, there's three approaches to dealing with this problem. One is to use the text around the images, such as with an HTML document that has photos embedded in it. This is the technique used by the image searches provided by Google, Yahoo, and the other search giants.
Another is to have users provide labels for all the pictures. Flickr (which was recently acquired by Yahoo) is the best known and most successful of these. Users at Flickr "tag" photos with short keywords. But there are others, including the cute little ESP game by Luis von Ahn and others researchers at CMU.
A third approach is to analyze the images themselves to identify characteristics of the images and transfer descriptions and labels from similar images. To my knowledge, most of this work is still in the research stage.
Once you have data about the images, you can search, but there's still the question of how to order the search results, what you do for relevance rank. For images embedded in web documents, you might be able to use the PageRank of the document, but Flickr and other photo services have no web documents associated with the photos.
Stewart Butterfield at Flickr just announced a new feature he calls "interestingness" and John Battelle calls "PhotoRank". It sounds like it cleverly uses the data from the Flickr community to do relevance rank:
Interestingness is a ranking algorithm based on user behavior around the photos taking into account some obvious things like how many users add the photo to their favorites and some subtle things like the relationship between the person who uploaded the photo and the people who are commenting (plus a whole bunch of secret sauce).Mmm... Secret sauce. Seriously, I'd love to hear the details behind this. Doing relevance rank for photos like this is a hard problem. It sounds like Flickr has a great idea for how to help people search for interesting photos.
Update: Brian Dennis posts some thoughts on "interestingness" and links to several discussion threads on the feature.