It would be most natural to say neither "that" nor "where", and just go straight with "the one he stayed in during his trip to Norway."
However, if you have to choose between these two options, the correct one would be "that", because it goes with the "in". With "where", you don't say the "in", since the sense of location is provided by "where".
The hotel where I stayed had free continental breakfast.
The hotel [that] I stayed in had free continental breakfast.