Could you also say "meu primo trabalha numa padaria"? I don't see the point of the "O" at the beginning of the sentence.
Is "numa" actually written, or purely colloquial?
Yes. The contraction is almost always used in Portugal, and still common in Brazil.
But just to clarify, would you see it in a newspaper/formal writing?
In Portugal yes, in Brazil the non-contracted form is probably more common, some authors believe the contractions don't sound "elegant", but it's not wrong either, just a matter of personal preference.
What would it look like in non-contracted from?
"O meu primo trabalha em uma padaria."