Below are a number of great resources for finding and applying for graduate fellowships.
External Funding Databases and Information Resources. These links include databases, such as the UCLA GRAPES database, that can help you find very specific fellowship opportunities. There are fellowships just for American Indians and Alaska Natives. There are intercampus collaboration fellowships on specific topics. These are worth a look.
Top Ten Fellowship and Scholarship Opportunities for International Students Many of the fellowship opportunities in American are limited to citizens; these links should provide a good starting point for international students looking for external support.
Advice for Science Fellowship Applications: NSF, NDSEG, Hertz by Philip Guo, Assistant Professor of Computer Science at University of Rochester
How to Write Grants in the Arts and Humanities from the University of Colorado. These tips also apply to writing fellowship applications.