Cecelia Pegasus's first appearance was as a portrait within Pegasus' bedroom at the Duelist Kingdom, followed by two flashbacks during "Jagshamesh!", while Yugi Mutou and his friends scoped out his room.
It is revealed in Pegasus's diary that he met Cecelia when they were still children. He instantly fell in love with her after concluding she was the second most beautiful person he had ever laid eyes on. (The first being him, of course.) However, during their wedding ceremony years later, she "suddenly exploded" at the altar.
It would take a trip to Egypt, where he acquired the Millennium Eye, for Pegasus to reunite with Cecelia. Though they had finally been reunited, she suddenly exploded again.
During the third meeting of the Council of Evil, Pegasus finally resurrects Cecelia (with the help of Rebecca's Teddy). Unfortunately, she is resurrected as a zombie and has the occasional craving for brains.