Вчера был густой туман над рекой.

Adjectives in Russian agree with the noun they modify in gender, number, and case. Here туман is a masculine, singular noun in the nominative case (because it’s the subject of был). Therefore, the masculine nominative form of the adjective густой is used.

• Feminine would be густая (e.g. густая мгла)
• Neuter: густое (e.g. густое облако)
• Plural: густые (e.g. густые облака)

Рекой is the instrumental case of река (river). The preposition над (“above/over”) requires the instrumental case when you indicate location:

• над домом – over the house
• над рекой – over the river
  Using the prepositional case (о реке) or accusative (реку) after над would be ungrammatical in standard Russian.

Yes, Russian word order is relatively flexible. You can move вчера to the beginning, middle, or end to shift emphasis or fit a style:

• Вчера был густой туман над рекой. (neutral)
• Был вчера густой туман над рекой. (emphasizes “yesterday” as new info)
• Был густой туман над рекой вчера. (more colloquial, last mention of time)
  All are grammatically correct, but the first option is the most neutral and common in speech and writing.

Both рекой and рекою are instrumental forms of река.

• рекой is the modern, most common form.
• рекою has an archaic or poetic feel.
  In everyday speech or writing, go with над рекой. Use рекою only if you want a literary or old-fashioned tone.

Here’s a rough guide:

• густой [goos-TOY] – stress on the second syllable
• туман [tu-MAHN] – stress on the second syllable
• над [nad] – one syllable
• рекой [rʲɪ-KOY] – stress on the second syllable
  Put it all together with natural Russian intonation:
  гу́стой тума́н над реко́й.

Yes. Russian has several words for fog/mist:

• туман (tuman) – neutral “fog”
• мгла (mgla) – poetic or literary “mist/darkness”
• дымка (dymka) – light haze
  For example: Вчера была густая мгла над рекой. Note that мгла is feminine, so you’d say была and густая.