Virginia has grown in size over the last 2 billion years. Volcanoes spewed lava onto the surface, oceans deposited sediments, continental collisions added clumps of land, and sediments eroded from uplands to form new land at the edge of the waters (or underneath the water). About 600 million years ago, the core of North America (the "craton") was much smaller than today's continental plate.
Virginia also got smaller. Continental collisions pushed rocks over each other and folded up Virginia like an accordion, pushing the Blue Ridge west and compressing the Shenandoah Valley. Throughout the entire time, erosion has carved into the land and ocean currents have carried sediments away.
That's the basic process, and it affected the entire eastern coast of North America. The crystalline bedrock underneath the more-recent limestone in Florida was once part of Africa, for example. That bedrock was part of Gondwanaland (the African plate), before it smashed into Laurentia (the North American plate) to form Pangea. When the continents split up, the Florida chunk of the African plate was left behind, attached to North America. Some Rice Krispies stayed with the Cheerios.1
Now put on your thinking cap and follow the links below.
(Whew, did you look at all three? Long description, lots of words... and it's only a short, not-exactly-perfect abbreviated version. Considering that you covered 1.8 billion years in a few minutes, that's a pretty good compression ratio.)
much of Virginia has been added to the core "craton" of North America over the last 600 million years, as limestone reefs grew on the continent's edge and through collisions with other tectonic plates
Source: US Geological Survey (USGS), The North American continent