I have a brand new oven/stove that runs on propane. Everytime I try to use the oven it ends up making the kitchen smell like that black soot carbon. I also can see inside the oven tall flames on either side of the bottom. I don't know if the flame is to come way up high like that. It is also orange yellow flames. My stove top flames have a yellow color as well and make the bottom of my pans all black and nasty with soot. Someone told me I have to have the flames adjusted but I don't know.
This sounds very likely a "gas" stove which has not had a propane conversion. Propane is run at a higher pressure than natural gas so all burner orifices must be down sized. Often stoves will come with a propane conversion kit included but sometimes you need to order one separately. Symptoms of a non-converted stove are large yellow flames. Correct flames should be blue with the tiniest tips yellow.
Everything where I am runs on propane- we do not have natural gas. Every gas (versus electric) appliance we install needs to have a propane conversion done to it. On a stove this entails changing the gas orifices in all cooktop burners, the oven burner, the broiler burner, and changing the orifice on the pressure regulator.
Do not use your stove until it is converted properly by someone who knows what they are doing (not a DIY thing). There is way too much flame and heat for how your appliance was designed. Serious possibility of a house fire.
If you are certain that the oven is set up for LPG (see the answer by Kyle), then another thing to check is that the air intake to the oven burner isn't blocked, for example by packaging materials that weren't removed when the oven was installed.
To get a good blue flame, you need a mixture of gas and air. That means there's an air intake next to the gas nozzle. If you ever used a Bunsen burner in school science, that's the holes at the base of the burner tube.
Both existing answers are accurate, but it's worth checking the regulator that's supplying the gas. It should be a fixed one giving the correct pressure for LPG, and may have a fault, making the whole thing even more dangerous. And at the same time, check the pipework for any leaks, too. Although that would make gas escape (dangerous) rather than suck air in. But with an outside leak, it may not be found easily.