There have been several interesting comments regarding the student/advisor relationship on my previous posts (here, here, and here) on co-authorship. It's clearly an issue that stirs up strong feelings in many, with several anonymous students (or ex-students) protesting do-nothing advisors who still put their names on the papers, and some anonymous advisors suggesting graduate students underestimate the value they provide.
I tried to do a little reading on the subject, and found some food for thought on my searches of the web. (References are very welcome in the comments; here's one and another and another and another, three articles and a guideline for students, that seem pretty good.) Most schools seem to have a basic official policy or guidelines in place. Some examples include this bit from the Harvard medical school, this from Duke, and this from Berkeley. The best I've found is this statement from Penn, which is amusing first because it seems to blatantly plagiarize directly from the (earlier dated) Berkeley one, but also because it links to the specific policies of individual departments. Indeed, one issue here is that is clear is that different fields seem to have different interpretations of what constitutes authorship, as well as different protocols for author ordering. The Berkeley/Penn statement go so far as to say, "In some fields, the Principal Investigator of the lab is first author of all publications." (Take that, graduate students!) So perhaps one issue is that computer science, as a relatively new field, hasn't set up its tradition for authorship and author ordering; as we've discussed, even within computer science, theorists default to alphabetical order while systems defaults to students first/ordered by contribution.
As far as official policies go, though, in general the authorship bar seems to be set intentionally low -- clearly tilted in the direction of advisors. While there is often a statement that each author should have contributed intellectually to the work -- which would not include just funding the project -- conception and design of the project is considered sufficient for that. (This seems to match "the PI rules the lab" mentality of some fields -- you may have done all the work, but the PI has set up the entire framework for what the lab works on, so that counts.) Similarly, while its generally understood that all authors should be involved in the writing, that can be limited to reviewing (and revising) the work. (PIs are, after all, too busy writing grant proposals to spend too much time on papers.)
As for my own opinion, I must admit, I'm on the side of the advisor. That's not surprising; after all, I am currently one. As a graduate student, I may have had my complaints about my advisor, but when I switched sides, I became a lot more understanding and sympathetic. In my experience, many graduate students do undervalue the contributions of their advisors, and the work they put into the students in general (and specific papers in particular). I'm not saying there aren't bad advisors out there, and that there aren't cases where advisors put names on papers they shouldn't, but my benefit of the doubt will tend to fall to the advisor.
Also, independent of the underlying ethical questions, my personal take is also that graduate students may not realize the "cost" of having your advisor on the paper is small. Whether using alphabetical order or by contribution, I think the default assumption is that the student was the "primary" author on a work unless other information is available (even when this assumption is unwarranted, which I think is a non-trivial fraction of the time). (Others may certainly disagree.) Here, again, recommendation letters and direct word-of-mouth, as well as longer established histories, are extremely important, moreso in my experience than who has their name on what papers.
We can, certainly, get back to arguing about what is the "right" answer, where the line should be drawn for an advisor to put their name on the paper. Or perhaps we should go to the extreme of having (as suggested in the HMS guidelines or the authors' guide for Nature) a small writeup for each paper where a description of each authors' contributions are provided. (Sarcasm note: as I'm sure I've previously stated, I would hate such a system.) More realistically, as these many guidelines all seem to state, authors need to talk about this and set expectations earlier in the process.
Where does this leave the unhappy graduate students? Ideally, entering graduate students should try to find out potential advisors' authorship policies before signing up -- ask the current students for an off-the-record honest appraisal. Or, ideally, graduate students should talk to their advisors if they have an issue -- let them know early on if you think you're writing a solo paper. If you've waited until the paper is being written, and then tell your advisor you don't think they've done enough, I don't think you've set up the situation appropriately.
And what should you do when your advisor says, "No, I'm the PI, my name goes on the paper."? As a practical matter, keeping in mind the strong advisor-oriented tilt of the authorship policies I've seen, realistically, I'd suggest finding a way to live with that, or find a different advisor who has expectations more in line with your own.