Learn Portuguese (Portugal): Já fomos à agência.

While you might sometimes hear it at the end in casual speech, já typically comes right before the verb in Portuguese. Saying Já fomos sounds much more natural than Fomos já.

I thought fomos was the past tense of ser (to be). Why does it mean "we went" here?

The verbs ir (to go) and ser (to be) share the exact same forms in the simple past tense! You have to tell them apart by context. Because this sentence is followed by à agência (to the agency), it is clearly indicating movement, so it has to be the verb ir.

Why does the a before agência have an accent pointing to the left (à)?

That accent indicates a contraction. The verb ir (to go) requires the preposition a (to) to show a destination. Since agência is a feminine noun, it uses the definite article a (the). When you combine the preposition a and the article a, they merge into à (to the).

How would I change this sentence to say "We haven't gone to the agency yet"?

You would replace já with ainda não (not yet). The sentence would become Ainda não fomos à agência. Just like já, the phrase ainda não usually goes right before the verb.