Learn Portuguese (Portugal): Nós moramos na mesma rua.

In Portuguese, when you talk about locations like a street, you usually say you live "in the" street rather than just "on" it. na is a mandatory contraction (blending) of the preposition em (in/on/at) and the feminine word for "the", which is a. We use na here because the word for street, rua, is feminine.

I thought describing words usually come after the noun in Portuguese. Why is mesma before rua?

You're right that most adjectives come after the noun in Portuguese (like carro vermelho for "red car"). However, mesmo / mesma (same) is a common exception. It almost always comes before the noun, just like it does in English. Notice that it also changes its ending to an "-a" to match the feminine noun rua.

Do I always have to say Nós (we), or can I leave it out?

You can leave it out! Because the verb ending in moramos can only belong to "we" in the present tense, it already tells us exactly who is doing the action. Portuguese speakers often drop the pronoun and simply say Moramos na mesma rua. Including Nós is completely correct, but leaving it out sounds very natural.