Some universities and faculty are more interested in getting undergraduates involved in research than others. I've had quite a few undergraduate students do research with me with great success (publications even). I've never taught at a university with a PhD in CS though - my institutions encouraged undergraduate research and often even provided funding for it.
I would recommend against approaching PhD students to work on their research unless directed to do so by their advisor - they are focusing their time and energy on finishing their degrees as well as any research/teaching duties assigned by the university. You can ask graduate students for advice on which professors are interested in working with undergraduates - they usually know the faculty pretty well.
As far as professors, there are a few different approaches. Your department should have research seminars - probably more than one - have you been attending? They are usually open to anyone who is interested and it's a good way to hear about interesting research. If the faculty member you are interested in working with has a research group with a seminar series then sitting in on that is also a good way to show that you're serious about doing research with them (but ask if that's ok!). Figure out a specific faculty member or research group you're interested in - you're more likely to get a positive response if you can demonstrate knowledge of what they are doing and genuine interest (in the research - not just in getting a recommendation letter!).
Does your department have programs for undergraduate research? Many have summer scholar programs that partner students with faculty or with research labs. Faculty who have grant money can often get extra funding to pay an undergraduate to work with them.
The other thing you can do is to look into Research Experience for Undergraduate programs - summer programs where you'd go to another university to do research. They are competitive to get into though so it's another situation where you'll need a letter of reference. This can be from someone whose class you've taken (I've written them for my students).