It didn't. The word originally came from French gratuit, which meant free (of charge). So a gratuity is something you give freely, when you actually don't have to (not really true anymore, because now it's expected, but a completely understandable semantic shift).
Both grace and gratuity came from the same root in Latin, which meant grace or thankfulness, but there was no shift from gracious to free. And the shift from thankfulness to gratuity is perfectly understandable. Going from thankfulness to a gift given because you are thankful would be metonymy.
The real question is why people started using it to mean graciousness in English, a meaning which it seems not to have had in French when we borrowed it (le Dictionnaire du Moyen Français says it meant gift or generosity), and which has since died out. My guess is that they recognized the Latin root gratia, one of whose meanings was grace.