Earthquakes can happen anywhere. While they're most common along tectonic plate boundaries (like the San Andreas Fault system - the boundary between the North American Plate and the Pacific Plate out in California), they can also occur in the middle of tectonic plates (geologists call them "intraplate earthquakes").
According to the United States Geological Survey (USGS) National Earthquake Information Center (NEIC), the epicenter of this quake was located at 37.936°N, 77.933°W, 5 miles from the small town of Mineral (38 miles NW of Richmond and 84 miles SW of Washington, D.C.). This was a shallow quake at 6 km of depth (3.7 miles) and it occurred at 1:51 pm EDT (1751 UTC).
This earthquake occurred as reverse faulting movement in an area called the Central Virginia Seismic Zone - a previously recognized area of seismic activity (albeit rare). Movement most likely occurred on an ancient NNE-oriented fault which was reactivated by modern-day stresses in the North American tectonic plate. These ancient buried faults are most-likely from the formation of the Appalachian Mountains by the collision of Africa with North America during the formation of Pangaea some 250 million years ago. This fault may have been inactive since then, simply remaining as a weak area in the crust that was reactivated by modern stresses.
Check out the following map. It was created by the USGS before this earthquake and shows the probability of a greater than 4.75 magnitude earthquake within next 100 years. It's about a 15-20% probabilty for the area where this quake occurred. Sometimes those odds pay off!
There have been about 200 earthquakes in Virginia over the past 25 years. Most are small and only detected by seismographs but larger ones are not unknown. The last comparable earthquake in Virginia (about the same magnitude as this one, we think) was on May 31, 1897 near Pearisburg in SW Virginia - a different seismic zone.
Earthquakes of this magnitude are rare 100 year events, but they do occur (something for people to keep in mind - no where's 100% safe).
Why was this earthquake felt in such a large area (basically from Georgia to Maine)? Because crustal rocks in the east are old, cold, and less fractured up then crustal rocks in places like California. In California, a 5.8 magnitude quake like this will be greatly attenuated with distance from the epicenter by these fractures. In the east, the mostly intact rock transmits the seismic energy much further.