Short answer:
- Know what area you want to work in and be fluent with it.
- Construct an honest, compelling narrative illustrating your strengths, how you've learned from mistakes or pitfalls, and why you're a good candidate for your chosen PhD programs.
- Talk to as many professors as you can about their interests and yours, especially those you'd like to work with.
More details:
There is some excellent advice here and here. Basically, Bradley Voytek (who is now a professor in neuroscience at UCSD) managed to get into UCSF (a top school for neuroscience) with an overall GPA that hovered around 2.5. As Bradley Voytek said, your ultimate goal is this:
Do everything in your power to leave a paper trail of excellence to
overcome your grades. Your goal is to make those grades look
meaningless. Your goal is to have your work speak for you so strongly
that, when people look at your grades, they feel silly for even giving
them a second thought.
This was precisely why I was willing to give my unofficial transcript to professors at my school who asked for them (when I needed letters of recommendation). They already knew me well enough to know that my GPA doesn't reflect my true ability.
As another suggestion, if you're applying for a school that puts a lot of weight on a subject GRE exam (like the Physics GRE), you can do your utmost to score obscenely high on the test and still get in. As an example, see this guy who managed to get into Harvard with a 3.1 GPA.
For the record, I'm an undergrad with a 3.16 GPA (with 3 grades of 0.0s and 3-4 courses I retook with grades of 3.0-3.1 on the retake because I didn't even bother going to class on either class attempt). Despite all this, I managed to get into both the University of Chicago and Brown University - both with fellowships for being one of the top applicants. I also almost got into Yale in a year that was unusually competitive for them (they paid for me to visit+interview there) - but there were research fit issues involved at the end (actually - what ended up happening was that I had such intensely-defined research interests - exoplanet climate modelling - that it would have been hard for anyone there to take me individually, and everyone felt that I would be going to Chicago anyways). Click here for a rough profile of my "stats".
You should also try schools that do interviews (especially in-person interviews) before they do acceptances, since the interview is where you have the opportunity to shine (and where they can at least give you a chance). Yale is one of those schools.
You should also look into very interdisciplinary graduate programs that are expanding faster than what their textbooks (and courses) can keep up with. Newer fields also tend to be low-consensus fields, which also tend to be more tolerant to those with low GPAs. The geosciences is one of the few areas where plenty of people with sub-3.5 GPAs often do get into top schools. As the geosciences aren't taught in high school, it's often said that the Geosciences is something that you "stumble" into, and it's actually very common for people to enter the geosciences only after finding that they didn't like another major (this is often true for geoscience professors as well).
Biology is another area that's often tolerant of those with low GPAs, from what I've heard. In both Biology and the Geosciences, research fit often matters a lot more than "being one of the top applicants", so if you have a focused interest that you've demonstrated through research (and that matches the interests of faculty members who are willing to take new students), then yes, they can be willing to take you over people with better GPAs and test scores. The thing in common with the two is that they're so broad that it's impossible to put every applicant through a common set of required courses (or through paper-based qualifying exams), so their quals cannot be based on coursework. In that case, performance in prior courses doesn't matter as much. In fact, some geoscience programs (like Berkeley EPS) don't even have admission committees because the interests of faculty members are so diverse that applicants often only have research fit with a single faculty member - so it then often becomes a single faculty member who decides between applicants.
The MIT Media Lab is the perfect example of this, in fact (though most geoscience/biology programs will have more of a committee than the MIT Media Lab). The tips in this link can be quite helpful to anyone with a low GPA who wants to work with a particular adviser.
You should also look for fields with very low people-to-problems ratios. Many of these fields don't offer courses that are part of the core requirements of numerous majors, so there won't be hordes of undergrads who take their courses. Fields like atmospheric science and various areas of biology are particularly known for their low people-to-problem ratios, and the professors in them can be incredibly accessible (and are more willing to closely look at unusual applicants). More here.
Also, just write 2000-word personal statements. I wrote 2000-word personal statements for all the schools I applied for (they were necessary since I had to do some explaining), and they didn't prevent me from getting in. They can annoy some schools, but that's going to be a matter of fact if you're a highly unusual applicant.
Finally, you can always stay somewhat longer. My GPA would never recover from the early mistakes I made, but I managed to recover by staying longer and by taking a huge number of grad-lvl courses in my last 2 years. When writing your personal statement, you should always put in statistics like last-2-year GPA and last-X-year major GPA in whatever field of study you're in (I put in post-(freshman year) physics GPA of 3.77 in). Be careful not to sound like you're cherry-picking though.
If you need some extra inspiration, you should read about Stephen Smale too.
He entered the University of Michigan in 1948. Initially, Smale was a
good student, placing into an honors calculus sequence taught by Bob
Thrall and earning himself A's. However, his sophomore and junior
years were marred with mediocre grades, mostly Bs, Cs and even an F in
nuclear physics. However, with some luck, Smale was accepted as a
graduate student at the University of Michigan's mathematics
department. Yet again, Smale performed poorly his first years, earning
a C average as a graduate student. It was only when the department
chair, Hildebrant, threatened to kick out Smale, that he began to work
hard. Smale finally earned his Ph.D. in 1957, under Raoul Bott.
One word of caution: Graduate programs have gotten a lot more competitive in the last few years, so what applied 5 years ago (or 40 years ago, for that matter), may not necessarily apply today.
By the way, elite private schools (for whatever reason) tend not to have GPA cutoffs. If you're a student with a low GPA applying for an elite private school, you probably have something else in you that's extremely unusual, since very few students with low GPAs apply to them. In fact, when I emailed professors, those at elite private schools seemed to be more responsive to my emails (low student to faculty ratio could be a reason behind that). That said, they're not necessarily more forgiving of unusual applicants. It's often the programs that have some "weakness" in their applicant pool that tend to be more forgiving of them.
Also - I would definitely look for areas where the department is trying to expand into, but where the department has no reputation for as of yet (visits/contacting professors can help you learn more about that).
Going to academic conferences can also really help as well - but only when you can make sure that you have useful things to say. The same is also true for visiting schools before applying.
