Senhor and Senhora are used to refer to names of saints.
Nosso Senhor means our lord, as in: Nosso Senhor Jesus Cristo, Our Lord Jesus Christ.
Senhora is lady: Nossa Senhora da Conceição. Our Lady of the Immaculate Conception.
Both terms mean the individuals in question are saints, except for Jesus, who is Lord.
In the case of Matosinhos, it's actually: a legend about a friend of Jesus who sculpted images of Jesus and threw them into the sea so they would not be destroyed and they washed up on the beach in Matosinhos. [in Portuguese, here is the explanation] http://magisterio6971.blogs.sapo.pt/114547.html
Often, images of Jesus or the Virgin Mary become associated with places or images and the names then become Nossa Senhora de Fátima, for instance. The actual meaning is the Virgin Mary who appeared to people in the town of Fátima.
Our Lady of the Hour. Hour refers to the time of the birth of Jesus, according to Infopédia.