I have some news that you're not going to want to hear: if you're applying to graduate school right now, you should simultaneously be applying for science fellowships. I know, I know, it's a huge pain, but they can ask you about it on your graduate applications ("Are you applying to scholarships like the NSF?") (most people say yes) and for the NSF, you have a much greater chance of getting it the second year you submit. UPDATE: NSF has changed the rules in 2016-- you're now only allowed to apply for the NSF one time once you've entered graduate school. No one has good advice yet for whether you should apply your first or second year.
I only applied to the NSF Fellowship, but the two other big ones for US students are the NDSEG and Hertz (which are even more competitive). See this post for some advice on international scholarships like the Rhodes and Marshall.
The good news is that the NSF application is pretty short. Something to keep in mind is that you need recommendation letters, and you really want someone / a few people to read these over before you submit, so you have to get started fairly early.
There are three websites which were hugely helpful in applying:
My biggest piece of advice is to read examples (read a LOT of examples) and to get feedback from friends. Google Docs are most useful :).
Good luck!