Does a prestigious internship (at google) help for PhD programs in Computer Science? If I have the option of choosing between a (non-research) internship at Google and a REU program at a non-prestigious university, which one should I select? After graduation, I intend to pursue a PhD in Computer Science, hopefully in machine learning. 

Which of the two offers should I accept to improve graduate admissions? What if the intern position is directly in what I want to work in, i.e. machine learning?

I know research is valued more for graduate admissions, but a machine learning internship at google seems like a valuable asset.
Take the internship. It's not so much about whether it helps for graduate admissions or not, but rather how it is going to broaden your horizons. If you do the REU program, when you start the PhD, you're going to be doing similar things. On the other hand taking the internship gives you firsthand experience you cannot otherwise get:


What working in the real world is like
What skills are actively useful in industry
What skills you currently lack, but can learn in a PhD
What kind of job you can do if you get a PhD, but can't do now


(This neglects the financial aspect entirely, plus the fact that you're still going to be learning things during the internship which you can write into your application.) These things are likely to change your view of the PhD entirely. In the extreme case, you might find you don't want to do a PhD anymore. Less extremely, you'll have a better idea why you're studying, what you want to learn, and how that is going to help you.

tl; dr: do the different thing, because it'll act as a great enabler even if it's not immediately helpful.