It feels like (and this may not have been your intention) this question kindof implies an understanding that humans and chickens coexisted for a time and humans didn't eat the chickens' eggs until they "decided" one day to try chicken eggs and decided they liked them and would continue the practice. It seems much more likely that humans inherited the practice of eating eggs from their pre-human ancestors. As to chickens specifically, modern domesticated chickens are considered the same species as wild "red junglefowl" from which they were domesticated. Red junglefowl are native to southeast Asia, and humans first made it to there probably between 35,000 and 50,000 years ago. So, if red junglefowl qualify as "chickens", I think the answer is highly likely that the first humans who encountered them in southeast Asia 35,000 to 50,000 years ago started eating their eggs because they weren't that different from the eggs of other birds they were already eating and found tasty.
The chicken is unique in that it wants to keep laying eggs until it fills its nest up, where other birds will just lay a set number. This means if you take the egg every day, you suddenly have an egg machine on your hands. Eggs being very nutritious, this is very advantageous. This made it one of the earlier domesticated animals we have evidence for.
It’s really easy to imagine it happening in a time before refrigeration.
Fermentation can happen quite fast, especially in warmer climates. My wife ferments mustard greens (similar to sauerkraut) for only a day or two depending on the temperature. It’s easy to imagine someone concluding “if a day tastes this good, I wonder what 5 days tastes like?”. And so on until they eventually recognize the preservative nature of fermenting.
Eggs are a typical foraging food. Our ancestors likely grabbed any eggs they could find when they could find them. Eventually we started farming in SE Asia and the ancestors of the chicken hung out near the plentiful feedstock of rice fields and made their nests nearby. Over time they got used to humans and we kept taking their eggs, as we had done when we found their eggs in the wild. Around 3,000 years ago we had the chicken, an easy to care for food pooping source of meat that we had bred to poop food regardless of time of year. The bird later spread all over the planet.
Fastfoward to more recent times and we have selectively bred and drugged up a bird that reliably poops food every day and can yield the maximum amount of meat possible.
We’ve probably always foraged eggs from birds from before we were even modern humans.
Eggs are an easy source of protein and calories that don’t take much of a fight.
Chances are the unfertilized egg (what we use today, generally,) probably got started being used when they domesticated chickens sometime around 5,000 BCE (iirc,) in south east Asia (where chickens were first domesticated.)
Egyptians, Greeks, Roman’s all had robust poultry. (even Mars loved him some fried chicken,)
For most of our history, we would have used everything we could from livestock, so it would have been a matter of time.