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, Kazuki's relationship with Coach Ohta is not only long distance, it very quickly becomes a Mayfly-December Romance because relativistic effects means that Kazuki 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.
Planetes often deals with this, given that most of its characters are astronauts working in orbit. Some relationships even get more long-distance than most when Hachimaki and Goro depart for Jupiter.
Film
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.
Live-Action TV
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.
Music
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").
Oral Tradition
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.
Video Games
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.
Webcomics
In Bittersweet Candy Bowl, the main character Mike is dating a girl named Sandy, who moved away when they were younger.
