The planet was first mentioned in Episode 2696 as an imaginary planet by Elmo and Telly Monster, shown to resemble a large jar of mayonnaise. The two bring up the planet again in a game of pretend in Episode 3096. Later, the planet was mentioned in imaginary scenarios by Elmo in Episode 3258, and by Big Bird in Episode 4037.
The planet was revealed to be a real location within the world of Sesame Street in Episode 3214, where a crew of Mayonnaisians ascend on planet Earth to discover a meal they can eat in the morning to give them energy throughout the day. They are given some plants (cornstalks) and livestock (a cow and chicken) to help the rest of Mayonnaise survive the morning.