"excavation in earth for reception of a dead body," Old English græf "grave; ditch, trench; cave," from Proto-Germanic *grafa-/graba- (source also of Old Saxon graf, Old Frisian gref, Old High German grab "grave, tomb;" Old Norse gröf "cave," Gothic graba "ditch"), cognate with Old Church Slavonic grobu "grave, tomb," and perhaps from a PIE root *ghrebh- (2) "to dig, to scratch, to scrape," related to Old English grafan "to dig" (see grave (v.)). Or perhaps a substratum word in Germanic and Balto-Slavic.
The normal mod. representation of OE. græf would be graff; the ME. disyllable grave, from which the standard mod. form descends, was prob. due to the especially frequent occurrence of the word in the dat. (locative) case. [OED]
From Middle Ages to 17c., they were temporary, crudely marked repositories from which the bones were removed to ossuaries after some years and the grave used for a fresh burial. "Perpetual graves" became common from c. 1650. Grave-side (n.) is from 1744. Grave-robber attested from 1757. To make (someone)turn in his grave "behave in some way that would have offended the dead person" is first recorded 1888.
Old English stan, used of common rocks, precious gems, concretions in the body, memorial stones, from Proto-Germanic *stainaz (source also of Old Norse steinn, Danish steen, Old Saxon sten, Old Frisian sten, Dutch steen, Old High German stein, German Stein, Gothic stains), from PIE *stoi-no-, suffixed form of root *stai- "stone," also "to thicken, stiffen" (source also of Sanskrit styayate "curdles, becomes hard;" Avestan stay- "heap;" Greek stear "fat, tallow," stia, stion "pebble;" Old Church Slavonic stena, Russian stiena "wall").
Sense of "testicle" is from late Old English. The British measure of weight (usually equal to 14 pounds) is from late 14c., originally a specific stone. Stone-fruit, one with a pit, is from 1520s. Stone's throw for "a short distance" is attested from 1580s. Stone Age is from 1864. To kill two birds with one stone is first attested 1650s. To leave no stone unturned is from 1540s.