Writing a story within a story guide

Purposes

So, what's the point of a story within a story? Why not just have the characters speak out relevant information or give the reader the required information through "regular" story telling? Well, there's plenty of reasons and one of them is character exposition and character development.

Character development/exposition

Having a character tell a story can reveal not only a lot about the story universe, but also a lot about the character telling the story. They way they speak, the way they interact with their crowd, the details they might alter, leave out or enhance, and so on.
Whenever a character tells a story it could also lead to background information a character might otherwise not reveal about themselves. A moment of vulnerability, perhaps over a drink or after having heard a painful story themselves, might lead to a character opening up about their past and this moment would be far more emotional and character revealing than simply giving the reader the information through descriptions and other kinds of story telling.

Background information

Background information is usually the main element of stories within stories. While you can give backstory through simple descriptions, which is often better for some information, it can be more powerful to give background information through a short story instead. Perhaps through a bonding moment around a campfire where the captain tells his soldiers what happened during one particular fight or perhaps an old man tells of the fate that befell the castle of which now only ruins are left.

Consider the following examples:
"Castle Arlok had fallen a hundred years ago during the War of the Winds. Its molten ruins could still be seen atop Mount Aranoc and served as a grim reminder of the power of dragons."
--
The old man stepped closer to the fire, his eyes lit up both from the flames and from a clear excitement that brewed within him as he began to tell his story.
"There were hundreds of them! Giant beasts with mouths of fire, each strong enough to take on a hundred men on their own and we were a mere 500 strong. But we didn't run, I tell you. Nay, we stood our ground and fought!".
Many of the regular bar patrons had heard the story a dozen times before, yet once more they were enthralled by the old man's story. The entire bar was silent, safe for the crackling of wood in the fire and the excited, raspy voice of the old man.

The first example isn't wrong by any means and it is often the way you'd give background information that isn't extremely important or just because there's a lot more to tell. But the second example makes a bigger spectacle out of it and helps build the world around it. It revealed people enjoy a good story, even if they've heard it all before, it revealed a bar can go quiet and might not be full of loud drunkards and so on.
Of course you can't do this for all background information as it'd make your story huge and overly bloated, but by making sure you pick the right background information and the right moment to tell it you can not only create a great story moment, you can also use it to change the pace of the story.

To give a further example of both these points, in the game The Witcher 3 there's a moment I personally love and is probably one of my favorite moments in The Witcher 3 as well as in games in general. Geralt, the protagonist of the story, eventually makes his way to a tavern where Priscilla, a poet, sings a song.
This moment is a change of pace in the rather hectic and violent story, but the lyrics of the song also reflect other elements of the story, it introduces us to a knew character in an interesting way and it shows what this world, as well as the main characters, think of poetry, or at least this poet in particular. Plus it's just a gorgeous song, I definitely recommend looking it up.

Perception of truth

Another thing a story within a story does is alter the perception of truth of the reader. In the previous two examples of the dragon attacks you can kind of assume the first one tells the truth, as it's usually the author who writes these bits and they wouldn't lie to you, right? Haha. But in the case of the second example the old man could definitely be exaggerating parts of the story and, let's be honest, he probably is. But what if he isn't? The fact these truths can be questioned can lead to interesting dynamics and potentially great reveals. What if the old man told the truth? What if the old man was the one responsible for all that destruction instead? What if the old man was in fact somebody who did run and, in doing so, caused the destruction and loss of life of countless others?

Whenever a character tells a story we only hear one side of that story and while they may tell the truth or think they are, it is only their personal perspective. Details of that story and the real truth could be revealed later or perhaps never.
To some extent this is the same as having a point-of-view character versus having an all knowing narrator. Both types have their merits of course.

Introducing a narrator

Speaking of narrators, having a story within a story can also give you an opportunity to introduce the main narrator of the entire store. It's been done in many stories and in many different forms. In Lord of the Rings the story you read is largely the story Bilbo (and later Frodo) writes in his book. In some Disney movies you're first introduced to the story universe through a narrator, like Clopin's song in The Hunchback of the Notre Dame and the mosaic windows with narration in The Beauty and the Beast.
The narrator might or might not show up again at the end of the main story, but by introducing a narrator this way you open up possibilities of mystery and doubt, depending on who the narrator is.

This specific technique is called a frame story, but I'll delve into this a little more later.

Parallels

In many cases the story within a story reflects or foreshadows events that are about to unfold in the main story. But this could be something that aids the characters in overcoming their obstacles as well. A group of adventurers seeking to destroy an evil and cunning dragon might learn of a different evil through a legend told by a travelling story teller. The evil in this story and, more importantly, the way that evil was defeated might give the adventurers a way to figure out how to defeat their dragon.

Of course it doesn't have to be this on the nose, but many stories make use of this to some extent. Information in books, stories told by the elders, folk legends and so on, they can all teach the main characters a lesson that might apply to their struggles. Whether you wish to turn these lessons into a fully fledged short story within your main story is up to you of course.

Deleted scenes

In some stories the little side stories are similar to bonus features or deleted scenes you'd find on a DVD or Blu-ray. It's pretty common to have an idea for a story, whether part of the same universe as your main story or something different completely, but you're just unable to make it fit or flesh it out completely. Some authors choose to use these as stories within stories instead. It doesn't work for everything of course and don't see this as an excuse to cram in every story idea you have, the little stories still have to fit in the main story after all. But it's definitely worth to think about this. If nothing else it might lead to new ideas and more world building.

How though?

So by now you might be wondering how to go about adding stories within stories. Unfortunately there's no straight forward answer to this as it is story dependent. Some might benefit from a travelling story teller, some from a wise grandparent, others from an exchange of ghost stories around a campfire or a dusty old tome in a library.
However, the main point to keep in mind is "What is the purpose of this story within a story?". If you know the answer to that it'll be easier to figure out how to add it.

Let's say the story within a story is supposed to reflect the opinion of the public regarding certain events. Well, perhaps a play about it might be best. Maybe a puppet show instead or an older person telling children a story of a supposed villain and a supposed hero. The puppet show is used in Gladiator (very briefly) and a play is used in Game of Thrones and in Avatar: The Last Airbender.
Now let's say the point of your side story is to alter the perception of a character. In this case a confession of sorts might work best or perhaps the reading of a book and the way that character interprets the story and uses the information within.

The possibilities are endless, which can make finding the right one tricky. But if you keep in mind the purpose of the side story and the other elements in your main story you'll definitely be able to find a suitable place and method of introducing a story within a story.

Frame story

I briefly mentioned frame story earlier and I think it's important to point out the difference between a story within a story and a frame story.
A story within a story can happen at any point, while the frame story happens at the beginning and potentially at the end. Hence the term frame story, as it wraps around the main story. In some cases you do come back to the narrator throughout the story, rather than just the beginning and end, but the biggest distinction is that a frame story begins the entire story instead of the main story.
In terms of whether you can, might or should use this it changes very little. It'll depend entirely on you, what you prefer and what you want from your entire story. If you're uncertain simply try out one method, if it doesn't work out you at least learned and gained some writing experience.