I can find close variants of the expression used as far back as the 16th century in English, and you'll find versions of the expressions in other language as well (several citations below are from the Early English Books Online database).

My guess (based on raising chickens) is that it's based on how hens walk when getting in and out of their nests (with careful steps). Or perhaps it's from when you're trying to find where your chickens hid their eggs, and need to walk gingerly in the area.

Discussion in the comments raises doubts about whether there's anything more to the question than the earliest attested use of the saying: the meaning is so obvious that there couldn't be too much to it getting coined. On the one hand, it's easy to work out the meaning. But on the other hand, it is metaphorical: people don't just walk on eggs. So I think there is some explanation, and "obvious" things are usually the hardest to explain.

Spatial layout and motion is a very common source for metaphorical meanings in all of the world's languages. In the expression we are talking about, the type of path that one walks on is being used metaphorically to describe someone's state of mind or approach to a social situation. It's not hard to find similar expressions of the walk on X type. I don't know which of these are conventionalized to the extent walk on eggshells is, but you get an idea of how productive the walk on X construction could be.

all thou canst do, is nothing, and this is to prepare the way for god, though in the meane tyme thou do nothing but drinke malmesy and walke vpon roses, and pray not word at all... (1630)
thou shalte walke vpon lyons and venomous edders / and shalte treade vnder thy fote the lyos whelpes and dragons:(1534)
the lord paues our way with thornes, lest wee should suppose our forefathers walked vpon pillowes (1623)
only i wil shew yt it is a verie slippery path wherein we may slide as soone as they that walke vppon ice (1588)
for alas we walk upon barrels of gun-powder in the day, our snares are so many; and we lie in the shaddow of death at night, our dangers are so great (1668)
and to their wives men give such narrow scopes, as if they meant to make them walke on ropes (1606)
the wayes of wickednes are slippery, and perplexed, we walk upon snares, we are compassed with briars, and pits (1668)
he considered that the wicked were set in locis lubricis, in slippery places: and like such as go upon ice, their feet would soon slide; or like such as walk on mines of powder

It is interesting to note that in two of these (walk on snares, walk on mines), the meaning is actually walk in a place where you are at risk of stepping on a snare, mine, etc. This makes it plausible that walk on eggs in Early Modern English meant to walk through a place where you might accidentally step on a fowl's nest, not literally to walk on a bed of eggs.

Examples and early attestations of "walk on eggs":

now last to you my legges, which be my bodies stay, frame not your gate as men on egges, Whome busting doth affray: nor yet so stoutly stride, as mens mens that beares would binde, for stately steps bewrayes the pride (1576)

The rocke of regard diuided into foure parts.

before they can be brought vnto it, they vse such a number of preambles, such vaunts and bragger; they speake so many things from the matter, and so litle to the purpose as is vncredible: and vvhen at length they come to the point it self, then lo, they treade so nicely and gingerly, as though they walked vpon eggs and feared they breaking of them, and a man can scarce turne his hand, but away they flie with such extreme hast, as though the deuil were at their heeles, and they feared lest they should stumble &; breake their necke at euery sillable which christ pronounced (1593)

A treatise conteyning the true catholike and apostolike faith of the holy sacrifice and sacrament ordeyned by Christ at his last Supper vvith a declaration of the Berengarian heresie renewed in our age: and an answere to certain sermons made by M. Robert Bruce minister of Edinburgh concerning this matter. By VVilliam Reynolde priest.

de fallu: surget amans, vestigia furum: suspenso gradus: and longest on the hinder foote he staid, so soft he treds, although his steps were wide, as though to tread on eggs he were afraid; and as he goes, he gropes on either side, to find the bed, with hands abroad displaid, and hauing found the bottome of the bed, he creepeth in, and forward go'th his head (1607)

Orlando furioso in English heroical verse, by Sr Iohn Haringto[n] of Bathe Knight.

nick: it must ope with farre lesse noise then cripple-gate, or your plots dasht: [.] [.] frank: so reach me my dake laorne to the rest, tread softly, softly: [.] [.] nick: i wil walke on Egges this pace: [.] [.] frank: a general scilence hath surprizd the house, and this is the last dore, astonishment, Feare and amazement, play against my hart, Euen as a madman beats vpon a drum (1607)

A woman kilde with kindnesse. Written by Tho. Heywood

for thou mayst many times discover a totty pate by the legs that bear it: to walk with thy nose erected, and thine arms always a kembow, like the ears of a pottage pot, will induce such as either meet or follow thee, to censure thee for a proud coxcomb: if thou tread mincingly with thick and short steps, as if thou wert walking upon eggs, they will be apt to believe that thou art a finical self conceited fool: let not thine arms as theirs do that are sowing corn, when thou goest, seem to walk as fast as thy legs, for this will make them account thee for a country-clown (1673)

Counsellor Manners, his last legacy to his son enriched and embellished with grave adviso's, pat histories, and ingenious proverbs, apologues, and apophthegms / by Josiah Dare.

The original idiomatic use of 'stay the course'

As phoog mentions in a comment above, the earliest instances of "stay the course" meant "to halt or temporarily impede a process." Thus, Ben Jonson, Volpone, or The Fox (1605) has this line:

Avocatore 1: Can you plead ought [that is, aught] to stay the course of justice? If you can, speak.

From "Certain Observations touching the two great Offices of the Seneschalsey or High-Stewardship, and High Constableship of England" (1641), in A Collection of Scarce and Valuable Tracts on the Most Entertaining Subjects, volume 5 (1811):

It is to be understood notwithstanding, that none may stop the course of any ordinary running streames within his banks or ditches longer then from the rising to the going down of the sunne. Neither may any one stay the course of waters with any new ponds, ditches, or sluces, but shall permit them to run their course, lest the mills standing upon their streams, or men in their affairs, tanners, diers, and such like, should thereby suffer losse and detriment. If any shall stay them for the filling up of pools, or ponds, they shall be bound to restore such losses as the milners, or others living by the passage of those waters, shall have sustained by the with-holding of them, and waters shall be suffered to run their accustomed course.

Two examples from the early nineteenth century involve ships and their progress through the sea. From Thomas Maurice, Indian Antiquities (1812):

By them [the Phoenicians], the ancient sails, which, in many instances, were made of nothing but hides, sewed together, were exchanged for more flexible ones of linen, and the leather thongs, or cords, used for bracing them and various other purposes, for others of hemp and flax. By them, too, the old clumsy anchors, which sometimes consisted only of a large stone, and sometimes of a log of wood, with a quantity of lead affixed, or a bushel of sand, let down to stay the course of the ship, were displaced for anchors of iron having at fist one, and afterwards two, teeth, or flukes.

And from Richard Pering, A Treatise on the Anchor ... and a Schedule of Proportionate Weights of Anchors (1819):

The most ancient anchors, we are told, were made of stone, and sometimes of a crooked piece of wood, to which lead was attached to make it sink, and to stay the course of the ship. These are not altogether thrown aside by the Chinese, in mooring their junks, even to this day. Afterwards anchors were constructed of iron, and furnished with flukes.

All the pretty horses

The use of "stay the course" in the very different sense of a horse completing a race appears for the first time in Google Books search results going back to 1885, in a citation in Farmer & Henley Slang and Its Analogues, volume 6 (1903):

STAY, ... Verb. (colloquial).—To endure, last out, or persevere : as an athlete in exercise, a horse in racing, an author in public favour. Hence STAYER = anybody or anything capable of holding on for a long time ; STAYING-POWER = capacity for endurance.

1885. D[aily] Tel[egraph], 14 Sep. He won at Lincoln ... and would STAY better than Pizarro. Ibid., 11 Nov. Doubts are also entertained concerning her ability to STAY the course.

By 1902, the phrase "stay the course" seems to have become thoroughly established in horse-racing lingo, but to have broadened to mean something like "compete successfully and finish well. From "The World of Sport," in The Sketch: A Journal of Art and Actuality (August 27, 1902):

The Irish colt, St. Brendan, is doing well in his work. He has good speed, and is certain to stay the course. The men of observation at Newmarket fancy Royal Lancer has a big chance. But he has been more or less under suspicion, and he is hardly likely to stay the course in a strong run race.

'Don't halt the course; hold to it!'

This was followed surprisingly quickly by yet another sense of "stay the course"—one very nearly diametrically opposed to the sense that prevailed between 1600 and the late 1800s: to continue on a particular course of action regardless of unexpected setbacks encountered along the way. The first instance appears to be in "Military Service Bill, Second Reading" (4 May 1916), in The Parliamentary Debates (official Report): House of Commons, third volume of Session 1916 (1916), which rather oddly shifts into that sense of "stay the course" from the racing sense:

Mr. HOLT: ... The policy of the large Army involves the policy of the knockout blow. It means that if you are going to have a large Army you have got to use it at once, and you have got to bring the War to a speedy termination, and the question which we have got to ask ourselves is whether, if we did this, we should be able to stay the course? ... I have always thought this was going to be a long war, and I want to be sure that we can stay the course. It has always seemed to me that when we started this War we were in the position of an athlete who had made the three mile race his special study, and who was suddenly asked to run on a quarter of mile course. The policy of shortening the course is a very dangerous one, and we ought to be quite satisfied that we can stay the course. I do not know what the present Chancellor of the Exchequer thinks of it, but I should have thought that anybody who knows, what is common property, the financial position of our friends, must be perfectly well aware that there is not the remotest chance of our being able to stay the course until the year 1918. We are not likely to stay the course until 1918 at out present rate of expenditure. Let us be satisfied on this subject.

And in Minutes Taken Before the Royal Commission on the Civil Service (1929–31) (31 January 1930) [combined snippets]:

[6674.] ... The principle seems to be this really, that all persons who pass the tests, other than the health tests, should be admitted to the Service, and the only differentiation against bad lives, apart from the sick-leave and so on, is that unless they stay the course they would not get a pension?

—Yes, but you see the difference between temporary personnel and outsiders who would come in under normal open recruitment is that the Departments have had an opportunity of testing the health records of the temporary staff. Those who have been in the service for 7 years would not be retained unless their health records were good.

6675. What you really mean is this: If you have a temporary who has been 7 or 8 years in the Service, it may be that on the first entry the health was unimpeachable. Where such people have spent 7 or 8 years in the Service as temporaries; you are suggesting that in the special circumstances of that case they ought to be regarded as persons who had passed in with a health certificate 7 or 8 years ago, at any rate to this extent, that if they stay the course, they should get a pension?

—Yes.

Here the notion of "stay the course" means (as it seems to have done in the speech about financing World War I) "sticking it out" or "seeing it through"—the modern meaning of the phrase.

But instances of the old usage continue to occur at least as late as 1980. For example, from Maurice Collis, Foreign Mud: Being an Account of the Opium Imbroglio at Canton in the 1830's (1946):

The [Chinese] Central Government was concerned to extirpate the whole traffic, not merely the riverine carriage of opium. His [Captain Elliot's] order for that to cease was only a palliative and one wholly insufficient to stay the course of events. It pleased no one; the Chinese were unsatisfied, and the British merchants felt that a Crown authority, by taking a stand against opium, though only in part, thereby admitted the wrongfulness of the whole, an admission which might be highly embarrassing in the future if, as was rumoured, the [Chinese] Court was determined to go to extremes.

And from Henry Dodwell, The Founder of Modern Egypt: A Study of Muhammad Ali (1980):

Near Tripolitza [in 1821] 3000 Greeks defeated 5000 Turks. The result was the surrender of that place and Navarino. At neither did the insurgents carry out the terms of the capitulation, and at Tripolitza they slaughtered 8000 Muslim men, women, and children. As a matter of course these events were followed bu like massacres of Greeks at Constantinople and elsewhere. The Greek patriarch and four of his bishops were hanged, and it was believed that at least one Greek life was taken for every Muslim that had perished in the Morea. The Shaikh-ul-Islam—the head of the theologians of Constantinople—was removed from his post for his unworthy conduct in seeking to stay the course of this revenge.

Interestingly, China Notes, volumes 14–23, pages 55 & 89 (1979[?]) [combined snippets] uses the phrase twice, in opposing senses, within 35 pages of one another:

But exorcizing the ghost of Mao has been a bitterly fought issue. Teng's drive for efficiency and modernization is cutting to the heart of the system the system Mao crafted in the 1960s and 1970s. This threatens some Chinese, bewilders others, and makes many cadres afraid to implement these bold initiatives until they are certain that the new program will survive its 74-year-old author. Teng believes that only direct repudiation of Mao's legacy of political radicalism will make these administrators confident that Teng's successors on the Politburo will stay the course, yet without their active support, the controversial new program will falter.

...

We have not realized that the violence of the revolutionary movement is but a reaction and a result of the seen and unseen violence of the present regime, and the reason why this revolutionary movement exists and has spread is that we have not done our duty in the reform of society, but rather have obstructed it and tried to stay the course of history, thus making Christianity into a tool of the reactionary forces in the world today.

The triumph of holding steady

In the United States, the decisive moment when the public embraced the (relatively) new meaning of "stay the course" and abandoned the old one seems to have occurred in 1982. In the off-year Congressional election (a federal election during a year when the Presidency was not being contested) in 1982, President Reagan, two years into his first term in office, made "Stay the Course" his rallying cry for electing Republicans to Congress to support his economic policies, which had run into some turbulence. The last gasp of the old understanding of "stay the course" came in this rather airily delivered note in Verbatim, volume 9 (1982) [combined snippets]:

When President Reagan exhorted Senators and Congressmen to stay the course, the actual meaning of his words was the opposite of his intended meaning. What President Reagan intended to say—and the American public no doubt understood him to mean—was that Congress should remain steady on the course it had set for itself. But what he actually said was that Congress should halt its course. For the transitive verb stay means stop, postpone or delay,' as in the locution to stay the execution.

The intransitive verb stay does carry the meaning President Reagan intended but like its synonym remain, it must be followed by an adverbial, not a direct object. No one would use remain as a transitive verb (e.g., "to remain the course"). To convey his intended meaning, President Reagan would have had to tell Congress to "stay on the course," just as he would have had to say "remain on the course."

But that's the funny thing about idioms, isn't it? In the event, the Verbatim writer was powerless to stay the course of linguistic change, as English speakers chose not to stay the course with the original meaning of "stay the course."