Fatooma is an old witch and was one of Genie's previous masters, or in this case "mistress".
Thousands of years ago Fatooma found Genie and used him for her own amusement. By the time it came to use her third wish, she realized she had fallen in love with Genie and so she desired to have her third wish be for Genie to love her and marry her. However this went against the Code of the Genie, not just due to manipulating love but due to that Genies cannot marry unless freed. This naturally put her on the spot as she had only one wish left. Genie then casually remarked that if he were free then he could marry her in an attempt to trick her into freeing him while not wishing for marriage. An excited Fatooma then thoughtlessly said that she only wished she could have a ring big enough for the wedding, to which Genie accepted as her third wish, ruining any plans she had for marriage as Genie was still imprisoned. She then angrily cursed out loud to be blown to Bermuda, which Genie granted as a "freebie", transporting her to Bermuda where she met a confused old wizard with a long beard who was vacationing there.
For the next 600 years, Fatooma used her witchcraft to travel all over the world and through time to try and find Genie, and finally did so 10,000 years into the future where Genie was now a free genie. Suffice it to say, it was a shocking reunion which left Genie in terror. Fatooma then revealed that Genie was obligated to marry her, as his "sarcastic remark" was treated as a promise by the Code of the Genie, which she had studied carefully, and all promises made by Genie during their time of service must be honored upon being set free. Leaving a horrified Genie with little options. She then took Genie back to her fortress where she planned to summon the Master of All Djinn to marry them. Luckily, Genie was rescued by Aladdin and Jasmine before that could happen, but Genie realized that a genie's word was his bond, and could not a break any promise. Aladdin however then gave Genie the idea to show Fatooma a "future vision" of their "wedded bliss", which he portrayed as a miserable marriage where an overworked Fatooma slaved away serving an incredibly lazy Genie while taking care of numerous children. Fatooma was horrified at the vision, making her give up on any thoughts of marriage.