OBTAIN PERMISSION FOR USE OF CELEBRITY IMAGES AND VIDEO.

Our company wishes to utilise popular celebrity images (and possibly video
footage) of celebrities in a new software application that we are
developing.  Where would we go to obtain permission for this?  And
what kind of royalties would we be expected to pay?

I think that while the first part of your question doesn't pose much
of a problem, your second one does. Answering a question like this is
impossible without investing much time and work. You might want to
have a look at the Google Answers pricing guide:
http://answers.google.com/answers/pricing.html

I recommend that you contact the agency that handles the artist. 

Vanessa O'Dea