While the deadlines for most fellowship applications may not be until November or December, much like college applications, summer is a great time to start thinking about them. For most fellowship, you will have to write a personal statement about why you want to be a scientist, as well as a research proposal of some sort (i.e., the kind of science you want to do). These two documents are the most significant part of your application (transcripts and letters of recommendation matter too, but not as much). Logically, you will want to polish these over time, and get input from others. This doesn't happen overnight, so it's better to start sooner than later.
While there are university-specific fellowships at some schools, I'm going to focus on the national level ones. Please note that these are the ones I found relevant when I was applying, and others may exist for those who are not computational materials scientists.
NSF Graduate Research Fellowship Program: This is probably the most well known of the US government fellowships. It is also one of the most challenging statements to write because of the Intellectual Merit and Broader Impacts requirements. It's less challenging to describe why the research you want to do is worthwhile, and why you're a good person to be doing it: this is something you probably think about anyway. Broader impacts, the impact of your work outside of the scientific community, is more challenging. Being involved with outreach programs is helpful, but you have to be able to effectively convey this briefly. You will quickly discover page limits are one of your biggest enemies.
Many universities offer seminars and help sessions for fellowship applications, especially NSF GRFP. Go to these!
The NSF GRFP is a 3 year fellowship, with $30,000 a year in stipend, plus tuition expenses. You can only apply during the first two years of your PhD program, but it is deferrable should you have money from another fellowship. I do not know if they will cover things like health insurance.
The Department of Defense has two major fellowship programs: NDSEG and SMART, which stand for National Defense Science and Engineering Graduate and Science, Mathematics and Research for Transformation, respectively. NDESG is a 3 year fellowship that increases slightly each year, from $30,500 to $31,500, which cannot be deferred. The fellowship also covers tuition, and up to $1000 of health insurance costs.
SMART can last for longer, but comes with a service requirement. During the summer term, you work at one of the DoD labs, and following graduation, you are contracted to work for the DoD for one year for each year of funding received. This is an excellent route for those interested in government service, since you are both supported as a student, and guaranteed a job at the end. You are funded at $25,000/year stipend plus tution.
If you have a TA requirement for your degree, this can be tricky to arrange with either DoD fellowship, as both limit your "other" funding to $5,000 a year without specific written requests.
The Department of Energy recently started offering a general graduate student fellowship[ in addition to their computational fellowship programs, the SCGF and CSGF respectively. The SCGF offers a stipend of $35,000 and tuition up to $10,500, as well as up to $5,000 a year to cover things like conference travel, research supplies, relevant books, and even some computer equipment. The fellowship must be renewed annually based on progress, with an annual conference for all DoE fellows. The CSGF has a stipend rate of $36,000 annually, payment of all tuition, and is annually renewable for up to four years. Teaching assistantships must be approved by the fellowship program.
Outside of the government, the Hertz Graduate Fellowship is funded at $31,000/9 months (unpaid summers), renewable for up to five years. However, it is limited to certain universities, so check if yours is on the list.
In the next part, I'll actually talk about some of the tips and tricks for successful applications. Tip One: Apply!
EDIT: Here's a list of additional fellowships mentioned in the comments: