Please feel free to edit the answer to improve it.
Generally, PhD programs in the US have many more applicants than they can accept. The number of positions is limited by finances (a department can only afford a limited number of RAs and TAs), space and resources (students often need offices and access to equipment), and the ability to supervise the students (there is a limit to the number of PhD students a faculty member can effectively supervise). The admissions committee must decide which of the qualified applicants are most likely to be successful researchers while taking departmental "politics" into consideration. These politics include things like the start up package for Professor X included a funded PhD student and a particular resource is already at capacity.
The admissions committee bases its decision on a number of pieces of information including GPA, GRE scores, statement of purpose, references and interviews and for international students TOEFL scores. There is no formula (e.g., 6*GPA+1*GRE+2*References+Publications) by which applicants are ranked, but some universities and/or departments set minimum requirements (e.g., GPA over 3.0 or a TOEFL over 85). The admissions committee looks at the entire application to make an informed judgement. This means that being strong in one area can, and does, offset being weak in another area.
GPA and major/background
When admissions committees consider the GPA they are considering a number of factors including the grades, the strength of the school and major, the types of classes, and trends. An applicant who did poorly in 1st year general electives will be looked at very differently from a student who did poorly in advanced specialized classes. The major is not nearly as important as the relevant classes. For example, an engineering department might look more favourably on a math major who took, and did well on, engineering and applied math electives than an engineering major who took humanities electives. As with everything in the admissions process, the admissions committee is trying to judge the potential for research success.
Compensating for a low GPA and major/background mismatch
A low GPA can be offset by a strong research record highlighted in the SOP and letters of reference. The SOP and letters of reference can also be used to make the admissions committee aware of any extenuating circumstances that may have lead to the low GPA. Similarly, the SOP and letters of reference can be used to address how your major and background prepare you for research in the field that you are applying to. Strong GRE scores can also help offset a low GPA, and a strong GRE subject test can compensate for mismatches between majors. The best way to offset a low GPA, or a mismatch in area of specialization, is to consider enrolling in a terminal Master's degree and getting a good GPA in difficult classes.
I would like to add that an excellent way of improving a low GPA is by taking a senior thesis course, which is almost always available. Not only is this a proven way of building close ties with one or more faculty members (who will supervise you in your thesis) and getting those strong, personalized recommendations, but it could lead to a publication, or at the very least, a technical report published by the department. My senior thesis experience was life-changing: I ended up doing a Ph.D. BECAUSE it made me realize that I was a better fit for doing research than I might have originally thought. In terms of grades, getting a good grade on the senior thesis course is usually not difficult (especially since you're not evaluated on an exam performance), assuming you put in the effort.
It is also important to think honestly about why certain grades are low, and what you would do differently in graduate school. Learning from failure is a crucial skill (see, e.g., Dweck's research on growth mindset, as well as her widely-read book). In fact, almost all academics have been rejected by some of the programs, fellowships, grants, and journals that they have applied for or submitted to, and many have even failed classes. Finding constructive ways to deal with negative feedback, rejection, and failure is crucial in academia.
Examine why you struggled or what went wrong and how you can address a problem like that in the future. How have you developed the knowledge and skills that would have helped you then? Depending on the kinds of problems you faced and the extent of their impact on your record, they may not be appropriate to mention in your SOP and through your recommenders' letters, but the steps you take to address them might tell their own story. (E.g., perhaps you failed a class but then did research with a professor of the same subject; perhaps you had a rocky college record because you were immature or bad at planning, but you have now worked for five years in a responsible position at a lab.)
There are a number of limitations to the GRE in terms of predicting research success, but it is the only standardized metric admissions committees have access to. The weight given to the different sections of the GRE and the subject tests can vary substantially among departments.
Compensating for low GRE scores
A low GRE score can be offset by a strong research record highlighted in the SOP and letters of reference. The SOP and letters of reference can also be used to make the admissions committee aware of any extenuating circumstances that may have led to the low GRE scores. A strong GPA can also help offset low GRE scores.
A particularly effective way to offset a low GRE is to retake the GRE. In many regions of the world, the GRE General Test is offered year-round via computerized administration at a testing center, and your scores are given to you immediately upon completion. Upon receiving a lower-than-expected GRE score, you can, and should, immediately register for another GRE exam and begin preparing. Because of the short turn-around time, any preparation you did for the previous GRE should allow you to prepare much more quickly this time.
You are technically permitted to take the GRE General Test once every 3 weeks, or 5 times a year. However, repeat testings are detrimental to your schedule, morale, and finances, so it might be best to keep taking the test only until you receive a satisfactory score that you feel will represent your target school's applicant criteria, not until you receive the best score you believe is possible for you.
Once you have received the score you are satisfied with, the ETS offers a service to allow you to selectively determine which scores you provide to schools you are applying to, called ScoreSelect. This way, you can present your best cumulative score to the applications committee without being concerned about an older test, or one where extenuating circumstances made you perform worse than expected.
After test day, you can send additional score reports for a fee, and select from these options for each report you'd like to send:
Most Recent option — Send your scores from your most recent test administration
All option — Send your scores from all test administrations in the last five years
Any option — Send your scores from one OR as many test administrations as you like from the last five years
You will select by specific test dates, so your scores are all from the same testing session.
This applies to both general and subject GREs.
The ScoreSelect option is available for both the GRE® revised General Test and GRE® Subject Tests, and can be used by anyone with reportable scores from the last five years.
Again, I want to add that, in my experience, the GRE (particularly the General GRE) is a 'filter', nothing more. In many cases, even low GREs will be considered and not automatically discarded. Most top admissions panels do not accept one candidate over another simply based on GRE. I know for a fact that some colleges don't even require candidates to submit GREs. When I was applying to CS Ph.D. programs a few years ago, for example, I noticed that MIT did not require GRE scores to be submitted.
In some fields, the Subject GRE is given significantly more weight than the General GRE, and so a low Subject Test score can be more harmful to a borderline application. Since the Subject Test is usually offered twice in the fall (September and October), it can be to your advantage to register for both sittings. This way, you can mitigate a poor showing on the September sitting by a stronger showing on the October sitting; and if the September sitting yields a satisfactory score, you can simply cancel your registration for the October sitting. This tactic can also be used for the General GRE in those regions of the world where computerized testing is not available.
Statement of Purpose (SOP)
Make sure you understand the conventions and expectations around statements of purpose in your field. In some fields, something fairly generic will suffice, and in others, it could be the DECISIVE component of your application. Talk to professors in the field you trust about whether your approach to the statement of purpose is an appropriate one.
This is also the 'fairest' part of your application. If you're passionate about the research you want to do, it will show up in your SOP unless you're a poor writer (in which case, you might want to reconsider the Ph.D. until you're a decent one; good writing/communication is essential for successful researchers). As I wrote in my own post down below, there are several proven techniques of getting a strong SOP. I'll detail some below, but be careful about your field, as these suggestions are definitely not appropriate in all cases. One approach you might take before you even start writing your SOP is to:
Select your research area and actively check out the profiles of relevant professors/post-docs/grad students (in that order) at the schools you are thinking of applying to. Check out their publications, and try to read (or at least skim) one representative publication before you start forming an opinion. The goals of this step are three-fold:
- (a) It will give you a good idea of how productive a research group is, and whether a professor is even accepting (or currently has) students. This is closely tied to the funding situation of that professor.
- (b) It will make you more informed about whether you really want to join that research group. What looks interesting at the high-level is not necessarily as exciting once you get into the nuts and bolts of the research.
- (c) If you discover a really good 'fit' (which is the best outcome of this exercise; trust me), you can use that in a big way in your application. In CS for example, students often post their code or demos. Download those and tinker with them. Apply them to new datasets. Have fun with what's available. I'm sure similar things can be done in other research areas.
After you have done (1), try to make contact with the faculty member of your choice. At the same time, also try to establish connections with the grad students. My adviser once showed me a list of potential Ph.D. candidates he was screening, and asked me if by chance I'd heard of any of them. As it turned out, I did know one, through early contact. Needless to say, she got the position. The rest of her application didn't even really matter at that point. Note that the reason you should do this step after (1) is to enable you to write an 'intelligent' note to the person you're contacting. It's a good idea to not mention that you're applying at all in your early emails. Instead, try to start a conversation around the actual research. Show that you're interested and that you know what you're talking about. (The "know what you're talking about" part is pretty important though!) Become a familiar name in that group.
...and finally, make sure to attend lots of talks by visiting faculty in your undergrad university. You don't know where that will lead you. If someone's talk influences you to pursue an area of research, that's an excellent thing to reference in your SOP.
How does all this relate to the SOP? Well, essentially the SOP is your (diplomatic) chance to show your committee that you did this and more. You can drop faculty names you've successfully contacted, and even reference papers. You can personalize each application. Most SOPs don't cite even a single paper. Citing a paper though will move your application up another notch in the eyes of an academic committee, but only if you do it intelligently and appropriately.
Having reviewed certain applications, I would also like to mention one major flaw that shows up in the majority of the SOPs that get rejected. The SOP is NOT the document where you should ever get too 'personal'. Don't waste too many words talking about how you want to be the next Albert Einstein. I'm not saying it should all be dry, but make every word as objective (and verifiable) as you can. This is generally true, but especially so for the STEM programs out there. Academics are impressed by crisp, concise writing.
Compensating for a poor SOP
Compensating for a poor SOP is very difficult. A high GPA and perfect GRE scores will do little to help an applicant who has difficulties writing about research. In some fields, past research experience is expected, while in other fields the ability to write about research intelligently may suffice in convincing the admissions committee to admit you, even if you don't have experience doing research. Strong letters of reference can, to some extent, address a weak statement of purpose. However, there is generally a strong correlation between the strength of letters of reference and past research experience. If you have no official research experience, try and get letters of recommendation from professors where you completed a class research project that got a good grade. Even if you didn't do supervised research with the professor, the professor may be able to comment on your research skills and successes. Definitely contact the professor and remind them of your class project, and the grade you received. Summarize it, and attach the project to the professor so they can refer to it.
You'll want at least one very strong reference for a top 10 program, and in many cases two strong letters (three is actually quite a stretch). See my note above for how you can secure at least one very strong letter by doing a senior thesis. Try also to aim for at least one research internship during your undergrad. This could lead to a second strong letter from a researcher in your area. Letters from industry don't usually have the same appeal for academics.
Compensating for a bad reference letters
Compensating for a bad interview
Improve your English and take the TOEFL again; generally schools have minimum TOEFL scores, and taking a student whose English isn't good enough can be a huge headache. Some schools in the US will do phone/Skype interviews with foreign prospective students to get a sense of their English.
Meeting the minimum requirements
Every university/department handles the stated minimum requirements differently. Sometimes a hard threshold is used such that if an application fails to meet all the minimum requirements, it will not be considered at all. Other times, the threshold is soft, and applications that do not meet all (or some) of the minimum requirements will still be considered. If you do not meet the minimum, only the department you are applying to can tell you if you are eligible to apply.