At the end of Mai-Hime, you can see Arika running across the background behind Mai and friends at springtime. This special only takes place a few weeks after that from Arika's dialogue about living in a tent.
Nina was always in Mai's class in Mai-Hime (seriously, she is even in the ED).
So...
Mai-Hime -> This Special -> 100s - 1000s of years and a planet or two later -> Mai Otome Sifr -> Mai Otome -> Mai Otome Zwei