The NSF Graduate Research Fellowship Program (GRF) is now accepting applications (through early November). The NSF GRF is the largest and most prestigious graduate fellowship program for the sciences in the USA. Approximately 1,000 fellowships, which cover tuition and pay a $30,500 stipend for 3 years, will be awarded again this year. Previous winners include Sergey Brin, Google co-founder (he list winning in his 3 paragraph bio on Google’s site).
The main site for the NSF GRFP includes the solicitation with details on applying and eligibility etc.. I can’t figure out how you find the application from the main site but here is the link to apply for the fellowship.
Advice is available online for applying for the fellowship: How to Win a Graduate Fellowship, Advice for Applicants to the NSF Graduate Research Fellowship and the University of Missouri provides a guide for completing an NSF FRF application.
You may use the coordinating officials directory to find a resource at your school to provide advice and assistance. You can search for those who won fellowships previously.
There is even a complete application from a winner of the fellowship online.

Pingback: Curious Cat Science and Engineering Blog » Bell Labs Graduate Research Fellowship Program
Pingback: Curious Cat Science and Engineering Blog » Ford Foundation Diversity Fellowships
Pingback: Curious Cat Science and Engineering Blog » Science and Engineering Internships for Summer 2007
Pingback: Curious Cat Science and Engineering Blog » SMART Fellowships