There are many helpful beginning points for your genealogy research in the Government Information Resources and Special Collections. Special Collections maintains a list of independent researchers who are familiar with their collections and with family research.
At the beginning of the Microfilm Guides Aisle in the Government Information Reading Room are a collection of volumes which should be helpful in your search for ancestors.
General Introductions to Genealogy
A Guide to Genealogical Resources at the University of Virginia - excellent web update to the printed Guide to Genealogical Sources in the Univerisity of Virginia Library below. The FIRST place a new genealogist should consult when using UVA's extensive resources.
Guide to Genealogical Research in the National Archives - GS 4.6/2:G 28/982 - Gov. Info Reading Room - Since many of the materials you'll need for your research are U.S. government records stored at the National Archives this volume will be very helpful. It provides a very good overview of census records, passenger lists, military records, naturalization papers, land claims, pension records, and other government records useful in tracing ancestors.
Virginia Genealogy: Sources & Resources, by Carol McGinnis - Z 1345 .M365 1993 - Gov. Info. Reading Room - A nice overview of records available for genealogical research, both in Virginia and more generally. This is probably the best book to start with if you're a beginner.
A Guide to Genealogical Sources in the University of Virginia Library - UPV 8/G28/977 - Gov. Info. Reading Room - While dated this slim volume provides guidance for beginning research at the UVA Libraries.
Alderman Library, 3rd Floor
University of Virginia