As far as I can tell, interactive stories were popularized in the 1980s by a series of books called Choose Your Own Adventure. These stories were written in the second person and featured reader choices (i.e. Turn right? go to page 2. Turn left? go to page 3). These choices influenced events in the stories and led to different endings. Interactive stories have since found a place on the internet; the choice format is easier to create and consume digitally than in a physical book.
What are some problems with interactive stories? First of all, second-person storytelling (also the format of role-playing games like Dungeons and Dragons) is limiting in some ways. The thoughts of the main character should not be stated because those thoughts are the reader's responsibility. The thoughts of other characters should not be stated unless the main character has a way of knowing them. Another limitation of second-person storytelling is that, since the reader is the main character, the story cannot rely on a main character with any consistency or particular arc. This is why the protagonist is often the blandest character in an RPG like Skyrim.
On the production side, the big problem with interactive stories is that, on one viewing, every player will only experience a fraction of the content created. An interactive story could contain 10,000 words, but any one path through the story would only be 6,000 words long. In other words, an interactive story that takes two hours to read takes much more work to create than a regular story that takes two hours to read. If the creator gives the reader too many plot-changing choices, the reader experiences an even smaller fraction of the content. If the reader has too few choices, they can feel like they are not in control and the point of an interactive story is lost.
How, then, can interactive stories be any good? The second-person storytelling, while limiting, can also be great for immersion. If the reader's character is engaged in political intrigue, for example, there's a great tension that comes when they have to interpret other character's motives by their visible actions and dialogue instead of being told what each character is doing and thinking. This idea isn't exclusive to interactive stories, but the blinders of second-person storytelling do a good job of placing a reader firmly inside the world their character lives in.
I have several opinions on the production cost of choice. I think that the best path to take is this: readers should, for the most part, not choose what happens to their character, but how their character responds. Rather than choosing whether to go left or right, for example, the reader should be told by some guards to go left and be allowed to choose whether they'll go willingly or kicking and screaming. This style of interactive story allows writers to work on one overarching story instead of dozens of branching stories. The reader can be engaged in this sort of story because they still have input: the burden of creation (in this case, the main character) goes from the writer to the reader. Readers should still be given some influence over the plot, but the biggest decisions should come near the end, so that the resulting story branches produced will be shorter. This is the style of the great Bioware role-playing games.
In many ways, most computer games are interactive stories. Looking at these stories in their simplest, choose-your-own-adventure format can help show the strengths and weaknesses of this genre for a digital age.