Tectonic plates have been moving and reshaping the earth's surface for 3.3 billion years.1
The chunk of crust that today includes Virginia has evolved dramatically over the last 2 billion years. Volcanoes have spewed lava onto the surface, oceans have deposited sediments, continental collisions have added clumps of land, and sediments have 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.
Though the North American plate has grown in size, Virginia also gotten smaller at times. 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 from Maine to Florida. Geologists refer to the North American plate (the Cheerios), plus the Taconic, Avalon, and other island arcs plus Gondwana (the Rice Crispies). When all the cereal clumps were together, they formed the supercontinent Pangea.
The limestones in the Shenandoah Valley and the igneous rocks in the core of the Blue Ridge are part of the original clump of Cheerios. Much of the eastern third of Virginia was added later, when clumps of Rice Crispies smushed into the Cheerios. That part of Virginia east of Great Falls on the Potomac River to Danville on the North Carolina border is "Rice Crispies" bedrock, formed from slices of crust left behind after collisions of island arcs and North Africa with the old continental core (the Cheerios).
The crystalline bedrock underneath the more-recent limestone in Florida was once part of Africa. That bedrock was part of the African plate (one of the clumps of Rice Crispies) before it smashed into the North American plate (the Cheerios). When the continents split up and the Atlantic Ocean formed, the Florida chunk of that African plate broke off and was left behind.2
The original chunk of Cheerios is about one billion years old. It expanded gradually on the edge, as limestone deposits accumulated in the adjacent ocean, for another 600 million years. Much of central and eastern Virginia, like the Florida bedrock, has been attached to North America for only the last 300 million years.
Great North Mountain (Shenandoah County)
(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.) Now check out:
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
Virginia is located near the middle of the North American tectonic plate, which stretches from the Mid-Atlantic Ridge to California -
but on the eastern edge of the portion of the plate that is not covered by the Atlantic Ocean
Source: National Oceanic and Atmospheric Administration (NOAA), Age of the Sea Floor with Shaded Vegetation and 20my contour