A few states, like Colorado, have boundaries based not on natural features, but entirely on the graticule of latitude and longitude (the rectangular grid that defines places in relation to the Prime Meridian of longitude running through Greenwich, England, plus the zero degree parallel of latitude at the equator).
Take a look at the state and county boundaries of Virginia, however:
In Virginia, the southern border was defined by the 36 degree 30 minute parallel of latitude, though the surveyors in the 1700's were less-than-perfect in marking the boundary to match the line. Most of Virginia's state and county boundaries are defined by a combination of natural features (especially rivers and divides) and straight survey lines. Two natural features form county boundaries along their entire length - the Blue Ridge (in blue) and the Rappahannock/Rapidan rivers (in white).
Most states, especially those created initially as English colonies, used natural features as the starting point even for the straight lines you see today on the map. In colonial charters, Maryland's western boundary was defined as a line extending north from the headspring of the Potomac River, while Pennsylvania's western boundary was defined as 5 degrees west of its eastern boundary. Not surprisingly, both colonies sought to define the starting point for those lines in a way that would maximize their territory... and reduce the size of Virginia.
Obviously the Atlantic Ocean marks the eastern boundary of Virginia, as Thomas Jefferson recorded in Notes on the State of Virginia. A non-natural, almost-straight line based on latitude marks the southern boundary with North Carolina. With a simple glance, it appears the Potomac River marks the northern boundary... though in fact there's more to that "edge" than meets the eye. And the western boundary, stretching from Loudoun to Lee counties - that's not a river, but is it based exclusively on watershed divides?
Accomack County's boundaries include Tangier Island and extend to the western edge of the Chesapeake Bay; the bay is not divided in the middle by county boundaries
Source: ESRI, ArcGIS Online