I've been meaning to write about applying for graduate fellowships for awhile. And I was about to do it too. Then I realized that Philip Guo already wrote an amazing post about it that explains the ins and outs of the NSF, NDSEG and Hertz fellowships better than I ever could. I applied for the NSF and NDSEG while doing grad school applications and didn't get either. The next year I read Philip's post before applying for all three and got the NSF, barely snagged the NDSEG and didn't even get an interview with the Hertz people.
The only tidbit that I can add is that the NSF isn't messing around when it comes to societal impact, and if you don't address it then game over. Ideally you should be able to mention a few concrete things that you've done. Many schools have outreach programs over the summer and could use a hand, so volunteer and have something to real to write about instead of that one time you helped your little sister on a homework problem.