I want to describe someone who comes from Norway. I feel like it's better to say "Norwegian native," but I'm almost certain that I've heard nouns come before "native," like in "San Francisco native." What's the best thing to do in this situation?
You're correct that Norwegian native is preferable to Norway native, but a native of Norway is your best option, so as to avoid alliteration. Kids on the playground would have many laughs saying "Norwe-e-gian native" a la Arnold Schwarzenegger.
Incidentally, I lived in San Francisco for 13 years and never once heard "San Franciscan native", but I took this to be an exception to the rule, perhaps to avoid confusion with the Franciscans.
The classic rule (American English) is that:
Compound nouns should only be formed with words of Germanic origin, as the very idea of using one noun as an adjective before another derives from German.
"Native" derives from Latin, and as such should be treated according to the grammatical preferences of its language of origin, producing "native of Norway". Nevertheless affixing -ian produces the adjective Norwegian, which gives the speaker another way of avoiding the formation of compound nouns with non-Germanic words while following the syntax preferences of German (i.e., adjective before noun).
It's all very complex and most people just go by what sounds right. You vacation in the South of France but you stop off in Southern Germany, and so on.