It's from Old Norse 'greiða'. An English cognate would be something like 'arede' (the a- prefix replaces the ge- which became y- in Middle English), from 'rede' (to give council/advice, set order).
The 'setting in order' meaning had the connotation of brushing hair even in Old Norse.
The verb 'to groom' comes from the noun, which meant 'attendant'. It is a variation of 'goom' from Old English 'guma' (man), cognate with Latin 'homo/hominis' (human).