Kristine Kochanski was a
Navigation officer aboard the
Jupiter Mining Corporation ship
Red Dwarf.
Third Technician Dave Lister fell madly in love with her during his tour there, and his quest to get her back and, as Kryten puts it, "move up and down on top of her in that strange fashion that humans find so agreeable" was a central part of his character in both the TV series or novelizations of Red Dwarf.
The story of the lovely Kochanski (who will forever in the hearts of true fans be Clare Grogan, with ludicrously pitched cap and huge hair) according to the books, at least, is that she and Lister dated for about two weeks, and found they had lots in common - she shared Lister's love for "It's a Wonderful Life", for example.
However, her ex came back and, well, she still had feelings for him, and thus poor old Listy was dumped. Whether Kochanski had true feelings for Lister is not made clear in the first book, because then the disaster strikes and she, along with everyone else dies.
The extended story from the books Better Than Life and Backwards steals the parallel universe concept of the famous 'Backwards' episode, melding it with that of the 'White Hole' and 'Polymorph'. Lister gets stranded on a planet near a white hole for almost forty years. The planet turns out to be Earth, but that's another story. Anyway, upon his rescue and their subsequent escape from the white hole's gravity, they are attacked by the polymorph and the aged Lister is killed by a heart attack.
Thinking fast, the crew send him into the backwards universe, so he suffers a heart attack and becomes alive again, and begins aging, in reverse. He discovers in the backwards universe that he is in fact married to Kochanski, and that they grow young together and unbirth two children, Jim and Bexley.
In the final book, Last Human, Lister and Kochanski are an item aboard the Starbug, and very passionately in love as well (quite how this didn't chagrin Rimmer and The Cat too much isn't really explained, especially as Kochanski is the ranking officer). After numerous misadventures they wind up passing through another black hole and are trapped on an uninhabited planet, as the only male and female couple. And thus, it falls to them to repopulate the human race as Lister, hoisting Kochanski triumphantly up in his arms, carries her off to some soft grass by a pond. Which, I feel is a suitably touching ending to the longest romance, ever. Awwww.