I've heard on several occasions that the most competitive applicants to fellowships and graduate schools start about a year before applications are due. I spent three years preparing my application! I suspect that most people don't spend this much time before they apply, but trust me, time is your friend. Ultimately, knowing that I wanted to go to graduate school early on was my distinct advantage.
I started writing my personal statement in my junior year (Fall '10) because I figured that it was the hardest part of the application. Unfortunately, this year was a bad one academically; I withdrew from core engineering courses and my overall GPA dipped below a 3.0. I was instantly unqualified to even apply for a fellowship or to a graduate program. Faced with this challenge, I strapped down and focused every effort on getting fully-funded at the graduate school of my choice.
With graduation pushed out further, I followed that year up with two consecutive Dean's List semesters. At this point, I still had no research experience, so I decided to study abroad in Brazil (Spring '12) where I could gain international exposure and work on a sustainable energy project. That plan didn't go as expected (I tell the story in my personal statement), so eight months passed by and I still hadn't done research. This pushed me to help my friend (a Ph.D. candidate) with her project. I made sure I understood what her project was about and designed a device that saved her time. This was non-traditional, but it was experience nonetheless.
The following spring semester, I took a co-op position at Argonne National Laboratory. This delayed graduation another semester, but I decided it was worth it. That summer, I secured an internship at Boeing in the Research & Technology division. Argonne taught me the basic skills necessary to conduct quality and ethical research as part of a research group. Boeing gave me perspective from the industrial side of research and a glimpse of conducting independent research. By the end of the summer, the hard part was already done and I was ready to apply. Still, in Fall 2013, I put in more effort by taking two technical electives that had a research project component.
Everything up to this point provided the story that I needed to tell in my personal, background, and goals statement. So, I chose not to try and explain away my bad junior year and I focused on providing a compelling narrative from there forward. I wrote my research proposal in three days by identifying a new problem to solve based on my previous research. I learned how to write a research proposal in the technical electives I took that fall.
(Side Note: My current research is unrelated to the research I proposed. Your interests may change and that is okay. Just do what you must to write a strong Graduate Research Statement.)
The key take away is that I made use of valuable time by specifically strengthening the weak areas in my application. I am 100% sure that I am not the only one that goes to this length of preparation for the NSF Fellowship. The competition is tough, but you can and will win if you put in the work.