Narrowly construed the OP question is easy to answer and is not really philosophical, it concerns the colloquial semantics of "put X on Y". According to which, whatever goes on top or on the surface is X, and whatever is underneath or in the middle is Y. Given the traditional ways of applying mayo it will be mayo that is put on the eggs. However, if an extravagant someone were to pour mayo on a plate, like whipped cream, and put egg on top, like a cherry, well, then we'll have some eggs on the mayo.
But I understand the philosophical pull of the question noted by the commenters. It is not unusual in philosophy when reflection on a mundane ("silly") question leads into deeper waters, and this one is structurally analogous to many philosophical questions with a long history. My first association was with the well-known story of Zhuangzi, an ancient Chinese Daoist, who dreamed himself as a butterfly and then mused if he was a man who dreamed of being a butterfly or a butterfly dreaming he was a man. The examples can be multiplied. What is the main dish and what is a cherry on top? What is the frame and what is an adornment? What is the main theme and what is an accompaniment? What is the core and what is the peel? What is the base and what is a superstructure (Marx's terms), or indeed what is reality and what is a dream?
One way to construe such questions is in Aristotelian terms of essence and accidence. The accidental is "put on" the essential as a contingent decoration. The essence, it goes, is what must be retained by the thing for it still to remain "that same thing", having a brain is essential to a human, but having a scar is not, the scar is just a put-on, an accident. Such a distinction is prominent in Kripke's version of modal logic. When it is said that A could have been otherwise the otherwise may only concern the accidental, in every possible world where a is present at all it must retain its essence, to still be A. It is essential to water to be H2O (but not essential to fill my sink), the essences are supposed to be written into nature, "carve nature at the joints", in Plato's metaphor.
But as the mayo/eggs example already shows the salience of the essence/accidence distinction can be challenged, a popular view is that it is merely a matter of perspective, purpose, interest, etc., which is which. A scar may be essential to some person's identity, they wouldn't be "the same" without it. A complementary view is that some things have no essence, only a cluster of traits any of which can be removed, although not all at once. This gives Wittgenstein's notion of family resemblance. And what Goodman said about resemblance may equally apply to essence, it is a useful notion in practical contexts, but "hopelessly ambiguous when turned loose".
Zhuangzi's and Marx's examples do not directly fit into the essence/accidence template, but they can be understood in related terms of logical or ontological priority, another old topic in philosophy. Under a common dependence model of priority, A is prior to B if B depends on A for its existence, and not vice versa, the cultural superstructure depends on the material base, argues Marx, but the converse influence is minor and inessential. Similarly, dreams essentially depend on reality, and not vice versa. But the same relativization dialectic as with the eggs and the mayo applies, could this be just one perspective among others?