The Graduate School just announced that applications for fellowships will be due on march 4, 2011. You can find descriptions of the different fellowships as well as a links to some other potential funding sources on the Graduate School’s website. Keep in mind that each fellowship has specific criteria and instructions for application. I believe that all of them must be routed through the department, so you should talk to your advisor or major professor as soon as possible if you feel that you might qualify for one. Good luck!
CLARIFICATION: With the exception of the Yates Dissertation Fellowship, all of the Graduate School Fellowships are for incoming students. I encourage you to explore the external fellowships and other funding sources to see if any apply to you. Sorry about any confusion on this matter.