Of course the most interesting part of the SODA conference (and generally all conferences) is the conversations one has out in the halls. At some point in talking to one of the many people job-hunting this year, my own employment history arose, and at the risk of self-indulgence I thought it might be instructional to repeat here.
When I was finishing graduate school, the job market wasn't great. Most people went into postdocs. Your Jon Kleinbergs and David Kargers got jobs, of course, but most top 36 schools weren't hiring theorists out of graduate school. I felt pretty fortunate; I had interned at Digital Systems Research Center (SRC -- which, sadly, is now before-many-people's time...), and it seemed reasonably likely I might be offered a job. I also applied for several postdocs just in case, and applied to a small number of universities. I avoided a wide search, figuring my chances were small, and that I'd rather do a postdoc than take a job somewhere I didn't really want to go.
I got a small number of faculty job interviews -- including an interview at Harvard. But, at the end of the day, no academic offers. I did, happily, get a job at SRC. I think from the perspective of many graduate students, this would be seen as a failure -- no faculty job! (In telling the story at SODA, the look in the student's eyes seemed to suggest that interpretation.) In hindsight, of course, it's easy to see that this was far and away the best possible thing for me. SRC was a great place to be, full of innovative people and a strong ethic of theory/systems collaboration, and I received the benefits of mentoring from many great researchers (particularly Andrei Broder), as well as time to develop my research abilities and profile.
I decided to throw my hat in the ring again two years later. Since I liked SRC, I again only applied a small number of places that I might conceivably leave SRC for. I got 3 interviews. And just one job offer, at Harvard, which had rejected me last time around.
I suppose in this rambling anecdote I'm hoping there are some messages job-seekers current and future might take away. Patience really is a virtue; you needn't get to where you're going immediately. (It seems many CS theory folks have had long, winding, and quite pleasant careers.) For many, it might be beneficial to have some time and experience before facing the pressures of the tenure clock. You should never take it personally if you don't get an interview or a job offer. Don't be afraid to fail. Summer internships are a very good thing. Research labs are a very good thing.
I'm sure many job-seekers, having gone from undergrad right to grad school, feel the pressure to get to right to the next step, a tenure-track position. It might not work out that way. But there are many paths to a happy career; I hope you don't get so tied up in the process that you stop enjoying what you're doing.