A frame story is a story that contains other stories. It is distinct from a series of stories that fit into a larger arc, which is the typical tabletop RPG (Battlestar Galactica is a famous television story with a series arc).
Some of the most famous frame stories include Canterbury Tales, 1001 Arabian Nights and Interview with the Vampire. Kill Bill was a fantastic frame story about a quest for revenge, with each target of The Bride's revenge being another story set in the frame, contributing to the frame story.
So you can see, what counts as frame stories are a continuum from something like Kill Bill, where the frame story is the primary story with a series of inset stories supporting it, to Canterbury Tales, where the frame story is just an excuse to have a series of unconnected sub-stories, to The Princess Bride, where the frame is barely present and only used to color the stories contained within, to Hyperion, The Usual Suspects or Forrest Gump where the frame provides a twist or resolution to the sub-stories.
In classic history-telling frame stories, the frame is "contemporary" and the sub-stories are historical to the frame. In Kill Bill and The Call of Cthulhu, for instance, the sub-stories happened in the past. In The Call of Cthulhu, it happened to someone other than the point of view character. These are history-telling stories. Many mystery stories are history-telling frame stories, where there are several persons of interest, and the investigator goes from person to person getting their history with the victim. Clues within each story point to which one is the real killer.
In fiction-telling frame stories, the frame is used to tell stories that are fictional within the frame, like Canterbury Tales and 1001 Arabian Nights. The Wizard of Oz and Alice's Adventures in Wonderland blur this line a little.
A typical tabletop RPG campaign is often like Star Trek or Battlestar Galactica, where the story is framed by a "series plot" or "campaign plot" in an RPG. But because the sub-stories are not stories told by or about characters inside the story, they're not really frame stories.
So... How can we use frame stories in tabletop RPGs?
Frames for Color
The easiest way to use a frame story is to use a color frame, like The Princess Bride. The book and movie use different frames, but the movie is clearer: A grandfather reads a book to his sick grandson, coloring the story as a whimsical fairy tale from the start. Interview with the Vampire uses a frame for color as well, setting the gothic tone of the sub-story. In this sort of frame, the frame story is very much secondary to the sub-story, the real story.
Frame to Play with the Fourth Wall
Video games often use a frame to play with the fourth wall. In Bastion or The Bard's Tale the player experiences someone telling a story to him about what's happening in the game. In Prince of Persia: Sands of Time, the protagonist is narrating his own tale. When you die in the game, he says "No, wait, that's now how it happened!" Frame stories in other media use the frame to give us an important fact: the protagonist is still alive. This colors the sub-story so that the audience knows that threats to the protagonist's survival are not meant to be the main source of thrills - the stakes depend on some other outcome. A GM can use a frame story like this to emphasize or de-emphasize dramatic elements. A GM can also use this sort of story frame to justify meta-game mechanics and genre conventions. Do you want to run D&D with item shops and level-ups happening mid adventure, lightheartedly emphasizing fantasy genre tropes and anachronistic speech? Build a frame story about a group of people playing a MMORPG.
You can also use a frame story to justify rotating GMs. Every GM has a different style, so every adventure will be different. Why not frame all of the sub-stories in a Canterbury Tales style storytelling contest? Then either use the same characters in each story (a team of heroes boasting about their adventures in different taverns), or have the characters engage in a contest to tell a fictional heroic adventure story about the other characters (e.g. Fighter tells the story of Wizard, Cleric, Barbarian and Thief), or use entirely different characters for each sub-story.
The "24 Hours Ago..." Frame
Frequently used in television, start with the characters in a very bad situation, then rewind to the beginning and tell the story of how they got there, then conclude the story by getting them out of their pickle. This sort of frame story could be especially awesome for tabletop RPGs. Players hate losing, so starting there frees them to play a story that ultimately ends with them in a bind. But the object of the sub-story is for the players to build up allies and resources that they can then call on to escape the conundrum of the frame story. Example: The heroes start in cells in a secret dungeon, locked up and about to be sacrificed to Asmodeus. Then you flash back to 24 hours ago, where the heroes are trying to find a way into the Shrine of Asmodeus. Eventually they learn that the only way to get close to the High Priest of Asmodeus is to pretend to be peasants and be captured by his goons looking for easy marks for human sacrifice. So they spend part of the adventure smuggling in their weapons and armor, concealing lockpicks in the dwarf's beard, etc.
Series of One Shots
Like rotating GMs, you can use a frame story to run a series of one-off stories, like 1001 Arabian Nights. Or you can tell a series of one-off stories about the same group of protagonists like The Adventures of Baron Munchaussen. The frame gives some shared context and allows you to connect elements from one adventure to the next, even though they're unrelated.
An ambitious use of the frame story is to tell nested stories, like in Frankenstein or The Historian. Nested stories can go quite deep, with a contemporary story, a sub-story, and a sub-sub-story. Each nested story uses an entirely different party of protagonists. Group A goes on adventure A1, where they meet Group B, who tells the story of their adventure B2, where they find the journals of deceased Group C, which tell the story of ill-fated their adventure C3, which tells Group B something they need to know so that they can survive adventure B4, which tells Group A something they need to know so that they can conclude the campaign with adventure A5. Over the course of the campaign, the players play three different characters, each.
Another ambitious use of the frame story would be to tell a mystery story. The challenge of this setup is to tell a story where different "five man bands" are suspects, so that the sub-stories can engage all of the players. For instance, a team of investigators on Babylon 5 is trying to find out who killed an ambassador. They interview three groups of suspects who had run-ins with him: A group of black market smugglers, a shadowy team of psi corps, and a rival alien ambassador and his staff. Each of these is actually innocent. Each tells their story, and in each story, the players take on the new characters and experience the sub-adventure. Each sub-adventure has a clue that, given together, point at the real killer. Then the investigator team has to catch the killer, undue her shadowy plans, and arrest her.
A large, complicated historical event like the Age of Sail (real world history), or The Clone Wars (Star Wars), or the Anarch Revolt (Vampire) spans continents (or star systems!) and many different social groups with different perspectives (merchants, various national navies, pirates, jedi, clone troopers, smugglers, loyalists, anarchs, inquisitors). You can use the frame of the historical event to tell the story of various groups that experienced the event, so that you can let the players experience the event from different perspectives across time and space.
For instance, a Dutch East India Company armed merchantman in the Caribbean in 1795 would have a different perspective from a Spanish man o'war escorting treasure ships for the Third Coalition in the Mediterranean in 1803, compared to a privateer sloop in the Atlantic hunting Napoleon's gold in 1806 or an American heavy frigate defending Boston Harbor in 1812. Together, one adventure on each ship can allow a different player to take the role of Captain each time, and provide different historical perspectives of the Age of Sail and let players experience sailing ships of various kinds.