Perhaps Alice and Bob started out dating while they lived close together and one had to move away (far enough away that they can't see each other on a regular basis); perhaps they began the relationship through the mail (or, in more modern stories, over the Internet) and never met in real life at all (but may be planning to at some point).
At any rate, a story that has a long distance relationship often deals with its pitfalls, the #1 being that Absence Makes the Heart Go Yonder. If they've promised to reunite but one party takes his / her (generally his) time, it may result in I Will Wait for You; if outside pressures force the waiting party to be with someone else, this then becomes You Have Waited Long Enough.
In GunBuster, Kazumi's relationship with Coach Ohta is not only long distance, it very quickly becomes a Mayfly-December Romance because relativistic effects means that Kazumi will outlive Ohta (and most of human civilization, as a matter of fact) by a long shot.
During the Sailor Stars arc of Sailor Moon, Mamoru went to America to study, leaving Usagi behind for a large part of the series. (And then it turns out that Mamoru actually had his heart crystal stolen at the airport, and Usagi witnessed it, but she was so traumatized that she repressed this memory. In the anime it's slightly changed; Mamoru gets killed off a little after his plane took off, and since Usagi didn't see it she truly believed Mamoru wasn't able to contact her..)
A lesser example is Motoki and Reika. Reika agonizes over accepting a two-year trip to Africa because it will take her away from Motoki. He promises to wait and, after the usual monster attack, she goes. In a later season she returns, only to turn right around and go back to Africa again—this time for ten years.
The anime version of Marmalade Boy had this for a while, when Yuu takes a scholarship and goes to study in America leaving his girlfriend Miki behind. It didn't work very well though: they did their best to try mantaining their bond, but Miki is emotionally exhausted due to being pursued by other two guys and, after a rather tasteless prank from a Clingy Jealous Girl who's after Yuu, they break it off for a while.
In Kodomo no Omocha, Sana goes on an extended film project out in the woods and is plagued by rumors and angry fangirls of her colleague who hate her for apparently dating him; later, the prospect of her love interest Hayama going overseas to recuperate from serious injury is enough to send her into a Heroic BSOD, though eventually she comes to terms with it and they are reunited in the Distant Finale.
They try it again later when Haruto gets a job that requires him to move. He is initially encouraged when he finds out his senior at work has maintained a successful long distance relationship with her boyfriend for five years. Until she shows up at his apartment distraught and begging to sleep with him since she just broke up with her boyfriend. The distance was more emotional in her case. As much as she and her boyfriend loved each other, their dreams for the future were just incompatible. Her boyfriend wanted her to quit her job and move in with him so they could raise a family, and she wanted to stay at her job. They avoided confronting the issue for years, but it finally came to a head.
To which they once again break up.
In The Circumstances Leading To Waltraute's Marriage, the Valkyrie Waltraute marries the human Jack Elvan, but humans can't survive in Asgard due to the thin atmosphere and Waltraute has too many responsibilities to stay in Midgard for long. She visits Jack's house regularly for a date.
The film The Lake House has an interesting variant: the distance isn't in space so much as in time.
The movie Going the Distance is set around a couple trying to have a long distance relationship.
In L.M. Montgomery's Anne of Green Gables series, Anne and Gilbert carry on one for roughly three years, while he attends medical school and she teaches high school. Anne of Windy Poplars is composed entirely of Anne's letters to Gilbert while they are separated.
In Rilla of Ingleside, many of Anne and Gilbert's children carry on long distance relationships during World War I. The one emphasized, obviously, is Rilla's sort-of, unofficial (she's confused) long distance relationship with her childhood friend/crush Ken Ford.
In The 39 Clues, Amy Cahill and Evan Tolliver's long-distance relationship (carried on mostly via phone) starts after Amy takes off on a series of missions around the world.
Done to all the married couples on Defying Gravity, what with half of each pairing being in space for six years.
Ziva had one of these on NCIS - cue "sympathy" from jealous Tony, as well as comments from an ex-hooker suggesting that Ziva look closer to home. Now, who could she mean?
Friends: Chandler and Monica in Season 9, when Chandler is transferred to Tulsa. Being Happily Married and hating his job Chandler eventually quits so they can spend christmas together.
This trope is petty much the entire point of the show Ny-Lon, which is about a relationship between a girl in New York and a guy in London... which, naturally, leads to a break-up or major fight about how hard long distance relationships are just about every other episode so that one character can dramatically fly across the ocean to re-proclaim there love. Of course, in the end they break up anyway.
Stargate Universe takes this to another level, with multiple characters having left significant others on the other side of the universe. The communication stones make things easier. Camille Wray looks likely to stick with her partner, Sharon. Colonel Young's marriage, on the other hand, is less solid.
The X-Files: Mulder and Scully carry on a rather clumsily-written version of this trope in the show's final season.
Zoey 101: Chase and Zoey attempt this via webcam after she overhears Chase tell his roommates he's in love with her and they switch places in an attempt to be together, but after their video date fails, the come to the conclusion that it wont' work and resolve to try it for real when they're together again.
CSI: Crime Scene Investigation, post season 9. Grissom and Sara are married, but Sara is working at the lab in Vegas, while Grissom travels and researches and lectures.
Ted in How I Met Your Mother with Victoria, his first serious girlfriend in the series when she moves to Germany for a baking scholarship. Future!Ted tells us right from the start that long distance relationships never work. Including theirs.
On the Bruce Hornsby and the Range album The Way It Is, the narrator in "Every Little Kiss" is in one.
Long-distance relationships are the subjects of two Franz Ferdinand songs ("Come on Home" and "Eleanor Put Your Boots On").
Name a fairy tale where the Official Couple get together in the first few scenes, and one or the other will have to leave their lover behind for whatever reason. Cue Laser-Guided Amnesia.
The Tokimeki Memorial series has a couple of examples of this, most notably with Kaedeko Sakura in Tokimeki Memorial 2 and Chiharu Aoki in Tokimeki Memorial Girl's Side 1. Due to the series' alignment to the far end of the idealism's side of the Sliding Scale and its extremely strong Power of Love theme, they always work out in the end.
In some romantic endings from Fire Emblem, one half of a support-built couple goes back to his/her land of origin, but the other one visits them once in a while, and after some time they get officially together. Some of them are:
In The King of Fighters, the few leads we have of Yuki and Kyo's relationship after the Orochi saga implies that they went from Highschool Sweethearts to this. In the Maximum Impact series Kyo is seen calling her from several phone stalls in South Town, and in XIII the pre-fight dialogue between NESTS!Kyo and Athena implies that Yuki asked Athena to tell Kyo that she and others support him no matter what.
HK-47 in Knights of the Old Republic 2 states: "Definition: 'Love' is making a shot to the knees of a target 120 kilometers away using an Aratech sniper rifle with a tri-light scope... Love is knowing your target, putting them in your targeting reticule, and together, achieving a singular purpose against statistically long odds."
It's never explicitly stated, but it's implied that Walter and Lyn's relationship is this in Front Mission 5. Likewise for Darril and Elsa, the protagonists of FM 4, who got married in between 4 and 5.
In Bittersweet Candy Bowl, the main character Mike is dating a girl named Sandy, who moved away when they were younger.
A nonromantic example occurred in Kim Possible A Sitch in Time when Ron's family movies to Norway (courtousy of Future Shego). Despite Kim saying they can still make Team Possible work, two times, Ron shows up late to the mission, and when they're finally together, they're out of sync, so they regrettably agree that Kim should go solo. Fortunately, Ron accidentally hits the Reset Button and causes everything to go back to normal.
Ron was worried about a straighter version occurring after graduation, believing that the distance would ruin his relationship with Kim. Whatever happens, Word of God says they stay together forever.