I am chairing the search committee for Harvard this year, motivating me to comment on the view from the other side of the search process. Everything here should be taken as general commentary, my own opinion, not the opinion of my employer or this search committee, and not necessarily specific to our search, which of course I can't discuss in any detail. (The following comments are not theory-specific, though I use theory-examples.)
A general search begins with getting several hundred applications for a small number of interviews and an even smaller number of eventual offers. Candidate quality is quite high, to the point where it's very difficult to whittle the folders down to a number that can be reasonably considered for interviews. [I'm personally doubtful that there will be enough academic/research lab jobs available this year (in, say, North American academic institutions) for all the highly qualified candidates. All the good people will get a job, I'm sure -- perhaps just not in academia, or in research labs. We'll lose people to non-research industry. That's not necessarily a bad thing, but I'm sure there are plenty of people who would like to stay in research that won't be able to. Of course, even if you get an academic job, it's not clear these days there's enough research funding to go around for everyone, anyway...]
Candidates need to find a way to stand out. More precisely, their research record needs to stand out. Somehow, unfortunately, it's not even enough to have a number of papers in top-tier conferences. In theory, for example, there's a number of people with multiple FOCS/STOC/SODA papers. Let's hypothetically say there's a dozen candidates with 3 or more papers in top-tier conferences in an area. What will make you stand out as one of the top two or three that gets an interview?
Letter-writers confirming the quality of your research (and your contributions on multi-author papers) are one obvious answer, and this partially explains the often observed hiring bias in favor of students from top-tier institutions; they have top-tier letter-writers. It is, generally, helpful to come from a top-tier institution, but it's less clear that it matters which particular one. Research quantity is another way to stand out. Those rare extreme cases of people who manage to publish 20 or so papers in top conferences do get noticed, certainly.
Quality, however, matters much more than quantity. Are you working on exciting problems, that can have a significant impact in some way? Are you following the crowd, or getting ahead of it? In essence, the question is "What is candidate X famous for?" If there's a good answer to that question when you replace "candidate X" with your name, you're much more likely to get an interview. And the statement "Candidate X is famous for writing a lot of papers" isn't really sufficient in itself.
Finally, I think there are further intangibles that contribute to this notion of reputation that need to be thought about earlier on in graduate school that impact the hiring process. Giving good conference talks gets you and your work more notice, increasing the fame factor. Working with many people, including people from outside your home institution, increases the visibility of your work (and improves your collection of letters).
In the end, of course, all this advice seems obvious. Then again, being on the search committee and writing this up clarified it my mind, and will make me reflect on my own recent work practices.