Origins
A ruler and a rule are the same object. The word regular comes from Latin rēgulāris, meaning 'according to rule', from rēgula — a straight stick used for drawing lines. The physical tool became the abstract principle: what follows the ruler's edge is straight, orderly, regular.
The deeper root is Latin regere — 'to lead straight, to guide, to rule' — from Proto-Indo-European *h₃reǵ-, meaning 'to move in a straight line'. This root produced one of the largest word families in English. A regent directs a nation. A rector directs a parish. A regime is a system of direction. Regal means 'befitting one who directs'. Even right, through the Germanic branch, carries the sense of straightness and correctness.
Middle English
When regular first entered English in the 14th century, it described monks who lived under a religious rule — the regula of Saint Benedict, for instance. Regular clergy followed a fixed routine. Secular clergy did not. The modern sense of 'occurring at fixed intervals' descends directly from this monastic usage.
The journey from straight stick to abstract principle to everyday adjective spans two thousand years, yet the core meaning never shifted. Something regular is something that holds to the line.