All fellowships are open to students in Computer Science PhD programs. Also, these don't include fellowships with required after-graduate school participation (unless I've missed something), but do include fellowships with required (or strongly encouraged) internships.
- IBM Fellowship - Deadline: Open for nominations September 22, 2008 through October 31, 2008 (nomination by faculty member required). Eligibility: completed at least one year of a doctoral program. Award:tuition, fees, and stipend for one year (amount varies by country/region).
- For Women:
- Google's Anita Borg Scholarship - Deadline: check back in October 2008. Eligibility: entering senior year of undergraduate study or be enrolled in a full-time graduate program for 2008-2009 with at least a 3.5/4.0 GPA. Award: $10,000
- SWE Scholarships - Application information for 2009-2010 will be available in December.
- AAUW Fellowships - Many fellowships; one is a dissertation fellowship for which eligibility is restricted to those who have "completed all course work, passed all required preliminary examinations, and received approval for their research proposal or plan by Nov. 15, 2008."
- For Beginning Grad Students:
- AT&T Labs Fellowship Program - Eligibility: For women and underrepresented minorities.
- DOE Computational Science Graduate Fellowship- Deadline: check back in October 2008. Eligibility: US citizen or permanent resident, first or second year of graduate study and planning full-time PhD study. At university that doesn't require non-research activities (i.e. teaching). Award: 4-year yearly stipend of $32,400 and tuition and fees and additional money for conferences and computers.
- National Defense Science and Engineering Graduate Fellowship - Deadline: January 5, 2009. Eligibility: Only for students in the beginning of their graduate program.
- National Physical Science Consortium - Deadline: November 5.
- Microsoft Research Fellowship - Eligibility: For students entering their second or third year.
- NSF Graduate Research Fellowship Program - Deadline: November 5th. Eligibility: Student has completed no more than one year of graduate study by August 31, 2008.
- Hertz Foundation Fellowship Award - Eligibility: It seems that this is generally only awarded to senior undergrad students or first year graduate students. There is a list of acceptable schools.
Also useful: a comprehensive but outdated list of fellowships for the sciences in general, and a non-field specific site for fellowships.