With the help of meaningful subplots that contribute to the story's central theme(s). Either have these new characters interact with the main cast, or keep them entirely separate. Both ways work, but having all characters interact with the main cast binds the story together.
For example - in a story about WWII with an Allied soldier as a protagonist, you might have subplots including the Germans, innocent citizens or perhaps other Allied soldiers. Introduce a citizen in distress, only to be helped somewhere by the main protagonist. The intersecting paths work very well for most of the time. Your main motive must be to create order out of the thematic narrative. Daily life is often not ordered at all, and quite unpredictable, but you can't do that in a story. So just go ahead, make mistakes - choose the wrong characters, go back and write them out, and come up with new ones. Or just edit along the way as you see fit.
Leave some of the story out of the planning and let it grow organically. Introduce characters along the way. Write a story like you are reading it. Make it interesting - and go along with your impulse if you want to introduce a particular character.
All that aside, this is your idea, and hence your puzzle to work out - only then will your story be original. Don't worry if you get stuck - that's the job!