Learn Croatian: Traži stalan posao u Zagrebu. - He is looking for a permanent job in Zagreb.

It actually is in the accusative case! In Croatian, masculine nouns that are inanimate (objects or concepts, rather than living beings) have an accusative form that looks exactly the same as their nominative (subject) form. Because a job isn't a living thing, posao doesn't change its ending here.

Why is the adjective "stalan" used instead of "stalni"?

This shows the difference between indefinite and definite adjectives. Stalan is the indefinite form, so it translates to a permanent job. If the sentence used the definite form stalni, it would mean he is looking for the permanent job (a specific one that was likely already mentioned).

How do we know it means "He is looking" if there is no word for "he" in the sentence?

The verb traži is the third-person singular form, which covers "he", "she", or "it". In Croatian, subject pronouns like on (he) and ona (she) are usually left out unless you need to add emphasis or clarity. Depending on the wider context, this sentence could just as easily mean "She is looking for a permanent job."

Why is it "u Zagrebu" (locative) rather than "u Zagreb" (accusative)?

The preposition u takes the locative case when talking about a static location (answering the question "where?"). Using the locative u Zagrebu means the person is currently inside Zagreb doing the searching. If you used the accusative u Zagreb, it would imply motion toward a destination (answering "to where?"), which doesn't fit the action of looking for a job.