mid-13c., "fit for a king;" late 14c., "pertaining to a king," from Old French roial "royal, regal; splendid, magnificent" (12c., Modern French royal), from Latin regalis "of a king, kingly, royal, regal," from rex (genitive regis) "king," from PIE root *reg- "move in a straight line," with derivatives meaning "to direct in a straight line," thus "to lead, rule."
Meaning "thorough, total" attested from 1940s; that of "splendid, first-rate" from 1853. Battle royal (1670s) preserves the French custom of putting the adjective after the noun (as in attorney general); the sense of the adjective here is "on a grand scale" (compare pair-royal "three of a kind in cards or dice," c. 1600). The Royal Oak was a tree in Boscobel in Shropshire in which Charles II hid himself during flight after the Battle of Worcester in 1651. Sprigs of oak were worn to commemorate his restoration in 1660.