I find that yoga is one of the most relaxing and powerful activities I can do for myself, yet how exactly did yoga become yoga?
Yoga is not a religious practice, it is a spiritual practice. The sages in the ancient times meditated and deliberated on the nature of reality, of this world, of its origin, causes and so on. They identified Brahman as the root cause of this world which is of the nature of pure bliss (Tait. Up. 3.6). And only by uniting with Brahman that man become blissful. So they devised or perfected techniques like meditation, concentration, etc. to unite with Brahman. This process of union is called as Yoga. Yoga is a Sanskrit word derived from the root yuj which means to unite.
Through meditation they had found that in the body itself that Brahman resides:
svadehamaraṇiṃ kṛtvā praṇavaṃ cottarāraṇiṃ
dhyānanirmathanābhyāsāddevaṃ paśyennigūḍhavat [Sve. Up. - 1.14]
Making own body the lower wood, AUM (OM) is made the upper, Churning in meditation through practice, the divine is seen hidden under.
Like scientists perfect the techniques and methods they invent, the sages in the earlier times kept on perfecting different techniques of Yoga. Then Patanjali Rishi systematized things by forming the Yoga school of thought of which self restraint, meditation, concentration, samadhi, etc. were the eight limbs:
yama niyama āsana prāṇāyāma pratyāhāra
dhāraṇā dhyāna samādhayaḥ aṣṭau aṅgāni [PYS - 2.29]
The eight limbs of Union are self-restraint in actions, fixed observance, posture, regulation of energy, mind-control in sense engagements, concentration, meditation, and realization.
So in course of time different kinds of meditation techniques and physical practices were perfected by different sages and saints. They taught their discovered techniques to their disciples and formed a branch of Yoga. From Adinath originated the Hata Yoga techniques, sages like Shandilya and Narada advocated Bhakti Yoga (union with Brahman or God through devotion) and some saints like Sankaracharya advocated Jnana Yoga and so on.
And when all things got inter mixed by people and teachers of modern times who are not much advanced in spiritually, they gave it a religious outlook mixing one thing with the other. Even to that extent that simple physical exercises are now branded and called as Yoga. But anyway that's just obvious due to the effect of time. Over time the true value of things and knowledge tend to get extinct. And the thing is, one is not bound to believe in many religious stuff to follow the path of Yoga.