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.