I'm very grateful to be supported by a Graduate Research Fellowship from the National Science Foundation. I was selected in spring 2011, and my tenure begins in August 2011 and will last for three years. Many thanks to my teachers and mentors through the years, whose support and recommendation letters made this possible. Thanks also are due to the U.S. government and American taxpayers, whose financial support makes exciting advances in fundamental research possible.
I applied for the NSF fellowship as an undergraduate senior as well, and received an Honorable Mention.
I was also lucky to be offered an NDSEG fellowship as well in 2011, but I chose to decline and accept the NSF support instead, due to greater flexibility.
Successful applicants doubtlessly need to have reasonable grades and some previous research experience. But a 4.0 GPA and a publication in a top conference is definitely not necessary to receive an award (I didn't have either). To me, the two most crucial pieces of the application (in order) are (1) stellar recommendation letters, and (2) solid essays.
You can't do much about (1) except to choose your recommendation letter writers wisely. I would suggest choosing someone you *know* thinks highly of you and has the time to write a stand-out letter. This definitely doesn't have to be someone in your intended field of study (though a scientist or mathematician is probably a better choice than an art professor, of course). Start thinking about this early, and ask alums of your department/school for advice on which professors on your short list write good letters (this isn't always obvious).
Fortunately, you as the applicant have plenty of control over (2). Each of these fellowship competitions requires the applicant to submit several essays, usually one seemingly separate topics like previous research experience, personal career goals, and specific short-term research objectives. The best advice I received (thanks to Lynn Stein) was to use all the different essays to tell a single, coherent story about you. The essays should explicitly reference each other and build on shared themes. My essays below really try to do this (I think I did better in the 2011 submissions compared to 2010).
NSF specific advice: You should never underestimate the importance of the *broader impacts* rubric in your evaluations. One of the biggest differences in my application from when I got an Honorable Mention to when I received the award was that I upgraded my discussion of broader impacts in the research plan essay from a single paragraph to 2-3 paragraphs.
My Honorable Mention application essays are attached below, shared mostly as examples for prospective students.