Where to start

Hi everyone this is my first post. My GGFather came from Norway, His name I,m told is very common...Axel Johansen. He was, I am told, a seaman, who presumably met my GGMother while he was in South Shields and stayed here. He died in 1929 at the age of 69 I have no proof of this but that would give hm a dob.of 1860. Their first child was registered in 1891, and the first record I have of him is in the 1900 census where his country of birth is Norway with an aside that he is nationalised, I have heard from other family history channels that this is rarely true! Unfortunately I cant find any record of their marriage either, . I suppose the way to go would be to look for any nationalisation cert and burrow through crew lists at the PRO but If any member has a better idea I would be grateful