You can smoke in dedicated smoking areas outside, but it's actually not allowed to smoke on bus-/train stops/sidewalks etc. There are just no one to enforce it.

I guess the places where you get escorted from in the US are privately owned and not due to a law (but I could be wrong). The companies firing you for smoking might also have to do with a bit stronger labor laws in Norway :)