The bolts are torqued so that it actually stretches the steel, and it's that stretching force (called preload) that does the actual holding. Since the bolts are physically stretching you start introducing metal fatigue, so that's why they are replaced in critical components or where failure would be catastrophic. Engine components, high speed rotating assemblies, and certain pipe flange connections come to mind but it's a very common practice. Sometimes they use special washers too to increase the distance of the preload force.
Another factor is the higher carbon content of the steel used. As the grade number goes up the more carbon is added to the steel, making the steel more brittle but far harder, allowing a higher force to be resisted at a cost of toughness. Steel is fully hardened and then tempered, which adds ductility back by converting the grain structure a bit. Basically the carbon content determines how much heat treatment can change the properties, while the amount of tempering determines how hard or tough it is. A file is a good example, it's a high carbon steel that is left fully hardened. It will cut metals softer than it is, but its easy to accidently break by simply dropping it. But you can also heat it up hot enough that the hardness goes away so it's really tough but won't hold an edge (this is what happens to saw chain if used dull). High grade bolts are more like files than regular "soft" steel, with a high carbon content and heat treatment to increase the hardness to the desired strength, which is then stretched to an exact amount determined by said hardness. As you can imagine this is tricky to get just right, so you use new to eliminate the errors which could cause failure.
But that was a very good post.
