They were married after Larry saved her island from the evil genius and scientist Dr. Nonookee.
However, Larry failed to please her and keep her sex life interesting, after a few years (about two years total) she left him for another woman, Bobbi another Native of the island.
Years Later, Larry still fondly remembered his wife, but not so fondly how he lost her to Bobbi.
Behind the scenes
Kalalau isn't so much 'bisexual' as she is heterosexual turned lesbian stereotype trope. So offended by worst possible 'man' that she has turned off all interest towards men entirely. There is no indication that she was interested in women before that, and most sources seem to suggest that she was originally only into men.