You might have to go a year on loans if you plan on applying this cycle, since fellowships usually go up around fall, due in winter, and awarded next fall. Also, some fellowships I've encountered have restrictions where you need to have 2 years left of the degree if you're chosen and such, so check the eligibility criteria closely.
I thought the NSF GRFP does support MS students? I vaguely recall going through their list of chosen applicants and seeing some masters students on there.
Anyway, I would start with fellowships databases, such as the ones offered by Cornell and UCLA.
While applying to grad school, I looked around for external fellowships, and since my research is environmental-related, that's what I was looking for, so some of these may not pertain to you. Still, some external fellowships that support MS students that I know of are:
- EPA STAR (if your work is environmental-related)
- GEM Fellowship
- NPSC Fellowship
- Paul and Daisy Soros New Americans Fellowship (this is for immigrants or children of immigrants, but it's not area-specific)
- AAUW Selected Professions Fellowships (for women)
- Switzer Environmental Fellowship Program (for environmental-related research AND you must be attending grad school in California or New England)
- SMART Scholarship (I think you might be required to work for the DoD after graduation for a certain amount of time if you accept this)
I hope this helps in some way.