- Is it possible if I could get 4 letters of recommendation?
- How far in advance should I notify those who are writing my letters?
- Does activity on sites like Quora, Stack Exchange, and Reddit's AskScience (as well as a personal webpage/blog of one's research) count as public outreach?
I think it's helpful to understand how NSF graduate research fellowship applications are reviewed. [Caveat lector: This answer was written in 2012; the application requirements and the evaluation procedure have both changed significantly since then. I strongly recommending consulting someone who has been on the review panel more recently.]
Each application consists of the following components: a 2-page personal statement; a 2-page description of past research; a 2-page description of proposed future research, transcripts, and exactly three recommendation letters. If you attempt to send four, NSF simply refuses the fourth letter; on the other hand, if only two letters arrive by the deadline, your application is rejected without review.
All 10000+ applications are reviewed in a single three-day physical meeting. Applications are split into 30+ subject areas, each considered by a separate review panel. Each panel has 20-30 members and reviews 300-400 proposals. (All these figures are ballparky; panels vary in size depending on the number of applications.)
Before review, applications are divided into levels based on the applicants' time in graduate school: None (30%), less than a semester (30%), less than 12 months (30%), and more than 12 months (10%). All level-1 applications are reviewed together, then all level-2 applications, and so on. Expectations are significantly higher for more experienced applicants. The precise expectations obviously vary by discipline, but in computer science, pre-students need a credible research plan, early students need publishable results, and older students usually need multiple publications. The "more than 12 months" level is only for people with extenuating circumstances, like a significant change of field.
The 12-month limit counts time that applicants have actually been registered, not time since entering their first graduate program. So a student who started a PhD program in August 2011 and does not register for classes this summer will still be eligible in September 2012. If you want to apply in your second year, do not take classes your first summer.
Each review consists of a "letter grade" (excellent, very good, good, fair, or poor) and a narrative evaluation of "Intellectual Merit"; a letter grade and a narrative evaluation of "Broader Impact"; and an overall numerical score. The panelists use the numerical scores to cluster the applications into four categories: Yes (10%), Maybe (25%), Honorable Mention (5%), and No (60%). NSF uses the narrative evaluations to decide which Maybes get fellowships and which get honorable mentions.
Every proposal is reviewed twice, the proposals in the No pile are retired, and each of the remaining proposals is reviewed a third time. Thus, each reviewer reviews roughly 35-40 proposals. On average, each reviewer spends 20-30 minutes on each proposal. That's just enough time to read each of the documents once, make a snap judgement, and then assemble a narrative review from a pile of boilerplate sentences. It's brutal, especially because most applications are strong.
So anything you can do to make your reviewers' life easier will work to your advantage. Every component of your application should directly address each of the two main review criteria. In particular, all three statements and all three recommendation letters should include a paragraph describing intellectual merit, starting with the phrase Intellectual Merit in boldface type, and another paragraph describing broader impact, starting with the phrase Broader Impact in boldface type. Both paragraphs should say something specific, substantial, and credible.
For security/privacy reasons, the review panel does not have internet access; reviewers are not even permitted to use their own laptops. So if you use your StackExchange participation as an example of broader impact, be specific about how you participate; the panelists can't look up your answers or your reputation.
Another point to keep in mind is that reviewers are probably not experts in the applicant's chosen subdiscipline. An application by an aspiring astrophysicist studying planetary climatology (to make up a random example) might be reviewed by a high-energy astrophysicist, an expert in planetary formation, and a string theorist. Yes, your statements must include enough field-specific technical detail in your statements to be credible, but the overall goals and merits of your proposed research should be clear to a broader audience.
For fine details, it's always best to talk with faculty in your field who have experience with NSF fellowship winners, either as an advisor, a reference, or a panelist. (The most useful letters read "I have written reference letters for x NSF fellowship applicants, of which y were successful; I would rank this student among the top z of those fellowship winners.") It's also a good idea to talk with past fellowship winners in your (target) department; ask to read their applications and their reviews.
See also NSF's advice.
To riff of off JeffE's comment:
Although only three letters of recommendation are allowed to be considered, you should always have an "emergency" writer on backup just in case one of the other writers can't submit the letter on time for whatever reason (sudden illness, job change, etc.). You don't want to miss out on the opportunity because somebody else dropped the ball.
You should notify them as far in advance as is logistically possible. You should already know who your letter-writers will be; you should find out how much advance time they need now, so that you can plan accordingly in the fall.
While most of those sites would count as public reach, I don't think Academia.SE would fall under that rubric. Something discipline-specific, on the other hand, would.