What is the typical time period after which an incoming grad student is expected to start publishing? An incoming graduate student is typically required to help out as a TA, take courses both related to their research and required by the program, as well as to start reading up on the research topics in his field. Unless he has worked in the same research area prior to joining grad school, it is unlikely he would get any publishable results very soon after joining grad school. 

To avoid being depressed by this apparent lack of results in the first few semesters, it would be helpful to know what the adviser/admissions committee expects out of him in that time, and by when he would be expected to start having publishable results?

I'm interested in the answers related to Theoretical CS, but as always, I believe it would be applicable to any grad  student as well - so it should not be specific to this field.
This wil vary significantly according to advisor, but I'd say a typical plan is:


Years 1-2: coursework, begin research
Summer of year 2: Small research publications (in my field, 2-4 page conference proceedings, small steps)
Year 3: Get some real research done, more small papers
Year 4+: ~1/2 paper a year, ish


However, the variance may be too great for this to be meaningful. I have a friend who published 17 papers during his 6 year graduate student tenure, and I have a number of friends who published zero peer-reviewed papers during my grad school tenure. Take the numbers with a grain of salt.