career - 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.