A great job talk by itself won't guarantee you a job, but I've heard of many an instance where a bad talk has ruined a candidate's chances despite otherwise stellar credentials. A good job talk should achieve three goals.
- Explain your results.
- Explain why your results are important.
- Explain how you achieved your results.
Know your audience, usually a broad spectrum of computer scientists. You give a different talk to them than you would in a regular theory seminar. Motivation and intuitive explanations of your research are key.
Repeat the following mantra as you prepare your slides: Formulas bad. Pictures good. Formulas bad. Pictures good.
Give a practice talk in your own department. Invite some people from outside theory. Listen to the comments. Revise your talk. Repeat.