In this case it doesn't matter. You have 5 O2s on the reactant side. Those O2s are completely oxidized. The only thing that can happen to them is reduction.
Your last sentence can lead to confusion.
The O2s are being reduced and not oxidized. You mean they were oxidized before the reaction? Can you elaborate?
I didn't say they were being oxidized. "The only thing that can happen to them is reduction." Reduction = being reduced = gaining electrons.
In O2, how many oxygens is each oxygen bound to? One.
In CO2, how many oxygens is each oxygen bound to? Zero.
In H2O, how many oxygens is each oxygen bound to? Zero.
In C3H8, how many oxygens is C bound to? Zero.
In CO2, how many oxygens is C bound to? Two.
In O2, how many non-oxygens is each oxygen bound to? Zero.
In H2O, how many non-oxygens is each oxygen bound to? Two.
In CO2, how many non-oxygens is each oxygen bound to? One.
Therefore, propane is oxidized, and O2 is reduced.
Edit: I see where you might get confused now. What I was saying earlier was that, prior to the reaction, O2 was completely oxidized relative to everything else in the reaction. You must oxidize something (say, H2O) to make an oxidized substance like O2. If that's confusing, just ignore it. It's not that important.
When I'm doing redox problems, if I see oxygens and hydrogens moving around, I use the rule that more oxygens on the right than on the left means that it got oxidized. In addition, if something gains hydrogens, it was reduced. Obviously these rules don't work in reactions that don't have oxygen and hydrogen in them, but it is a useful shortcut (for me, at least) when there is oxygen and hydrogen. Propane became CO2, therefore propane was oxidized. O2 became H2O, therefore it was reduced.
You asked how we know if O2 gained a carbon or if propane gained an O2. It doesn't matter which way you think about it. O2 didn't gain an oxygen, so it was not oxidized. Propane did not gain any hydrogens or lose any oxygens, so it couldn't have been reduced.