Virginia is a place that many genealogists will eventually turn to in their quest for their ancestors, after all it is the place where a vast number of our country's roots were first formed. If you are having trouble with Virginia ancestors there are many different options available to you.
First remember that if the timing of your search is 1863 or after you may need to search in West Virginia for the records. The western counties of Virginia first became their own separate state on June 20, 1863. A lot of West Virginia records are housed in the West Virginia State Archives. Some records for birth, death, and marriage may be found within the archives site. Information about queries and research is also available here West Virginia Division of Culture and History.
The reverse also holds for searches for West Virginia records. Some records are available at the Library of Virginia The Library of Virginia some records are available online at this site so make sure that you make use of the search features to check for availability.
County boundaries also changed very frequently so do a little homework and find out what county you need to be searching for a particular time period. Also try to find out from what county or counties your particular county was formed.
The US GENWEB pages for Virginia and West Virginia may be especially helpful in your search for you ancestors at Smith Cemetery (Youngstown, IN) here you can access a page for each of the two Virginias, and from there the state pages have links to almost every county in each state.
One source for information that you may not be aware of is the research guides at http://www.familysearch.org/Eng/Search/RG/frameset_rhelps.asp and http://www.familysearch.org/Eng/Search/RG/frameset_rg.asp each one of these links gives you valuable information about searching for ancestors in each one of these states and some background information is included as well. These sites are a valuable resource for any genealogist.
Another invaluable resource is located at USGenWeb Census Project here you can scan through lists of census transcriptions. This is useful if you are searching one of the censuses on a commercial database web site and just cannot find your ancestor. I was able to take my research for a West Virginia ancestor back an additional decade just by going over the indexes found here. I was able to determine that the name was spelled in a way I had not thought of and actually gleaned valuable clues to other possibilities about this ancestor.
Research in the Virginias is particularly exciting because of all the historical emphasis placed upon this area. With these resources your have a basic toolkit for your research in the Virginias. Happy hunting.