Judging Ph.D. applications is not an easy task. Most of our applicants have near perfect grades (in math and TCS courses) and GRE scores (focusing on quantitative). Next I read the letters of recommendation. Nearly every recommender writes positive letters but you can definitely see some differences. "Best student in the past five years" means much more than "one of the top ten graduating CS students this year." Recommendation letters carry more weight if they show a personal contact not just "he took my class." I also pay particular attention to letters written by people I know, i.e., active members of the theoretical computer science community.
I check to see if an applicant has done any research as an undergrad (which helps but is not critical) and do a quick read of the statement of purpose. I know applicants fret considerably about the statement of purpose but in fact they carry very little weight. You can use them to explain anomalies in the application (health problems in the semester you got a C in algorithms). Trying to be clever can harm you. I remember one applicant years ago started the statement with "I want to be a graduate student because I don't want to work for a living."
Does it matter what undergraduate school you attended? We'll accept a student from any university or college, but I keep the quality of the school in mind as I evaluate the application.
Does it matter if you are a US citizen or even live in the US? Not really, though many universities including the University of Chicago have strict lower limits on TOEFL scores for incoming foreign students.
In short for me, assuming an applicant has good grades and scores, it is the letters of recommendation that make or break an application. Choose your letter writers well.