How important are publications for undergrads? I have heard vastly conflicting statements about whether undergrads applying for PhD programs should have published already, or what level of research will be expected of them. Looking at CVs of some of my school's professors, almost none of them seem to have publications from earlier than the 2nd half of their graduate studies, meaning they spent most of their time before getting their PhD without any publications or those that they had weren't worth listing, in their eyes.
Obviously, I'm going to try to get the best experience I can as an undergrad, and I hope that means getting published research, but in every area I've dipped my toe in, from probability to dynamical systems to complexity theory, the sheer amount of additional knowledge I'd need to understand even a upper-level graduate text seems intimidating.
When did you first publish, and what sort of research experience (if it's something other than publishing an article) should an undergraduate aiming for a PhD have?
Disclaimer: I'm an undergrad in CS, pretty average or maybe above average in my progress so far, and I'd like to make a career in researching some of the theoretical (and obviously math-heavy) parts of computer science, rather than software or interface.
 A: Based on several conversations I have had with CS grad students, I have the sense that in your field of preference (computer science theory), having published research work as an undegrad is very important if you want admission into the grad programs  of the very top schools. 
A: I will point out that when Robert Solovay got tenure at Berkeley, he had no published papers.
A: I'm director of graduate admissions for the math Ph.D. program at a research I department.  We are certainly interested in assessing research potential.  But we don't judge this by published papers; almost no undergrad has any, and when they do, the actual material they contain is usually not of great interest.
It could certainly be helpful to start exploring research.  You should do this under the supervision of a professor (whether at your own institution in the context of a thesis or capstone project, or at an REU) who will be able to attest, in a recommendation letter, that you are very likely to prove interesting theorems in the future. 
A: I'll just point out: I know successful mathematicians who had no publications accepted (and in at least one case, none submitted) when they finished grad school.  
A: I am (as always) speaking with regard to mathematics, not CS or or some other field:
Undergraduate publications are not viewed as a requirement, nor even necessarily a big plus, in a grad school application.  (By cosmic coincidence* I have a stack of grad school applications to look at tomorrow, so if I change my mind on this I'll let you know.)
There is something to the idea that undergraduate papers are more prevalent now than they used to be.  I think this is partly because the worldwide mathematical community is more connected and more collaborative now, so it is less critical to be in the right place at the right time in order to do undergraduate research.
The thing about undergraduate papers is that, unsurprisingly, they are most often not very good compared to papers written by more mathematically mature people.  (Of course there are some exceptions, my favorite being Furstenberg's one paragraph Monthly article which gives a topological proof of the infinitude of the prime numbers.  But even this, while brilliant, certainly does not represent his best work!)  There's also the suspicion -- whether true or not -- that the behind the scenes advisor (who may not even deign to appear as a coauthor on undergraduate work) is likely to be the brains behind the operation.
I think it is a good thing to try to do some research as an undergraduate -- I did a summer REU at Indiana University, which was great -- but to realize that it doesn't matter too much whether it gets written up and/or formally published.  Surely there should be a stage in one's mathematical training where one doesn't need to feel the pressure to publish!
*: Not really.  
A: Well... in answer to the personal question.  I ended up submitting my first paper about a year and a half into my PhD.  For various reasons, it took around two years before it got accepted.  
As a side note, I encountered a problem in my undergrad which I was unable to resolve until towards the end of my PhD - which I've now submitted for publication.
As for how much experience... actually, I don't think all that much experience is required - it is more important to find a suitable problem.  It needs to be largely unresolved, but have a reasonable chance to be open for attack without years of study.  If you're interested enough in the problem, as you study the problem and read other authors' articles, you will gain the necessary experience.
A: There is a situation where it might be helpful to have a publication.  If you're applying for a PhD at an overseas university, they might not be able to compare your grades with the standards of their school easily.  Having a publication might give you that extra something.
A: My advice (as a pure mathematician!) is that the best way to get going in research is to write mathematics, and rewrite it till you have got it clear to yourself. The composer Ravel once commented: "Do copy! If you have some originality, it will show itself. If not,  do not worry!"  In fact the originality may show itself at say the 5th rewrite, when the creaking wheels of the brain have been finally knocked into a little motion. 
I did an essay on set theory for a College prize, which helped in an exam question. As a PhD student, I most enjoyed working with a visiting researcher (Dick Swan) on notes of his lectures on sheaves. Much later, I stumbled on the area of groupoids by trying to write a new proof that the fundamental group of the circle was the integers, and writing and rewriting my proof made me see that the arguments should generalise to higher dimensions.  
Daniel Quillen was said to have written thousands of pages of notes as he tried to understand various areas, and put them in his own terms. 
The question of publication of what you have written is more problematic.
A: If you're reading advice that's meant for students in various fields, not just mathematics, you should keep that in mind.  I had lots of friends who published as undergrads.  But these were people in other fields (mostly chemistry) where they worked in a lab at some point as an undergrad and had done some part of the work that led to a paper.  We don't have positions analogous to those in mathematics (you can't "work in someone's lab") and so the expectations are different.
A: Regarding the fact that the professors whose CV's you looked at didn't have publications before grad school - bear in mind that they got their Phd's two decades or more ago. The amount of research experience and the number of papers published by undergrads in general may very well have gone up in the meanwhile. So while I doubt that publishing a paper is critical to getting into a good Phd program, I wouldn't be surprised if it is weighted more heavily today than in the past.
Other people here will probably be able to give you a much more informed opinion on this.
A: As for mathematics, it might be worth mentionning that there's an AMS prize rewarding undergraduates who published "outstanding" results (by themselves or as a joint work), the Frank and Brennie Morgan prize. 
That said, there is no indication on the number of candidates considered each year for the prize. Perhaps the fact that they have honorable mentions means that really only one or two undergraduates each year manage to publish at research-level, the rest of those publications not being worth mentionning.
A: If you like theoretical computer science, you should try to take some math classes. Maybe you'll even change your major because you like it so much! Anyway, this question is kinda vague for the following reason: If you publish a significant paper your last semester as an undergraduate, that's certainly more impressive than ten trivial papers published over the course of four years.
