Importance of single author papers?
In some fields (like e.g. Economics and Mathematics) single authored papers -are- a good thing to have when you go on the job market. In theoretical computer science, collaboration is much more common, and it is not unusual for even relatively senior researchers to have very few single authored papers. It is not at all suspicious if a student on the market has only papers with co-authors. This is partly because we publish more frequently, so it is ok that each individual paper has less signal about your specific contribution. This is not to say that single authored papers are not impressive, but credit is super-additive across authors, and all things being equal, you should prefer to have a better paper with more coauthors than a worse paper with fewer. This should push you towards collaboration, since collaborators make your research both more fun and generally stronger. 

Of course in hiring decisions, committees will attempt to figure out whether you were a significant contributor to the papers you worked on or not -- but this will be done largely through the letters you obtain. If you have several good papers with the same senior co-author, that coauthor should write a letter for you, since they can explain in detail your contribution. It also helps if you have a clear research agenda of your own. Many papers on -your- topic with a rotating cast of coauthors conveys that you are leading the research direction, in contrast to a series of papers on disparate topics, each in the research agenda of your various coauthors.