This is NOT a normal condition in any gas range. If you see soot accumulated on your oven cell walls, even a little, STOP USING IT AND GET IT CHECKED OUT!
Soot is a product of incomplete combustion. So is Carbon Monoxide (CO), dubbed "the silent killer" because it is odorless and kills by displacing oxygen in your blood, making you sleepy and, in high enough concentrations, can make you take that final dirt nap. We've all heard the stories of people dying in their homes from CO poisoning. Improperly adjusted gas appliances, like the oven shown in the photos above, is one of the more common ways this happens.
A standard practice in the appliance industry is that all gas appliances, ranges, ovens, dryers, etc., come ready to burn natural gas. If you're going to use propane (also abbreviated LP for "liquid propane"), you have to convert the gas system in the appliance to safely burn it without producing soot or unsafe levels of CO.
Since propane burns hotter than natural gas (2,500 Btu/cu ft for propane vs. 1,030 Btu/cu ft for natural gas), it needs more air to make a "complete" (or at least safe and soot-free) combustion. If the air-fuel ratio (AFR) is too low (too much fuel or "too rich" in automobile terms), you'll create soot and unsafe levels of CO. If you're interested in some numbers on the AFR for natural gas and propane, start here.
While no combustion is 100% complete, you can still get close enough to prevent soot formation and keep CO production to safe levels.
The range in this service call is a Kenmore (Frigidaire-built) range that was purchased from a famous, nationwide retail chain (I'll give you one guess; hint: it's a Kenmore). This range, like all gas appliances, came ready to burn natural gas and needed to be converted for use with propane.
The customer paid the retailer for the conversion but it wasn't done properly. They converted the gas burners on the cooktop correctly by replacing the gas metering spuds for each burner with the smaller diameter spuds sized for propane. But they completely neglected to convert either of the gas burners in the oven (bake and broil). Behold (click the images for a larger view):
To make matters even worse, when the customer called the retailer's customer service department to complain about the soot in the oven, they advised her to run the self clean feature which successfully produced copious amounts of soot and, at the 900F temperatures reached in the oven cell during self clean, baked the soot onto the oven walls. The soot will never come out. This range is only three years old and the oven is effectively ruined.
So how is the strange and mysterious conversion process done in gas ranges? It's really not a mystical experience at all. It's as simple as following the instructions and installing a few pieces that all manufacturers provide for this very purpose. For example, here is an official conversion instruction sheet that Frigidaire includes with the conversion kits for its ranges. GE's conversion instruction sheet has similar information but I think it's a little more comprehensive and easy-to-follow (you'll need to be an Appliantology Apprentice to download it).