Of course they don't use the word "Easter" (or any cognates) in Ukraine.

Russian folklore has it that the first dyed egg was "made" by Mary Magdalene, who was (for whatever reason) on trial before Caesar. And she said something along the lines of, 'If Christ is risen from the dead, may this egg in my hand [she presumably carried eggs with her from time to time] turn red.' And of course it did or this would be a really crappy bit of folklore. But at any rate that's why we dye eggs red (in Russia, at least in the "old days" (before the Bolsheviks), Pascha eggs were always red).