Most of my colleagues have talked about the most common source of funding for graduate students: research and teaching assistantship. However, I am going to take a different route and share some tips that helped get a highly competitive external fellowship.
Tip #1: Find someone that received a competitive fellowship and ask them if they will be open to share their materials with you. To be honest, most people will say no, but all you just need if for one person to agree. Once I got a successful application, it was not difficult to identify what I was missing.
Tip #2: Identify one of more faculty members that specialize in the area you are interested, and ask them if they will be willing to give feedback on your proposal. In my case, I approached a potential adviser and his comments played a fundamental role in improving the quality of my proposed research plan.
Tip #3: Apply to at least one fellowship that provides feedback to all applicants. Therefore, even if you get rejected, you will receive feedback on your application.
Tip #4: Keep applying until you are no longer eligible. If you applied Tip #3 you will get a sense on which fellowships to re-apply and those that you should not bother. Do not get discouraged!
Here is a link to some external awards: http://www.indiana.edu/~grdschl/external-awards.php