Learn Russian: Ночью мы решили идти берегом. - At night we decided to walk along the shore.

This is the bare instrumental of route. It is used with verbs of motion to show the physical path or space through which the movement happens. Here, it translates to "along the shore" or "by way of the shore".

Could we just say по берегу instead of берегом? What is the difference?

Yes, по берегу is very common and means essentially the same thing. Using the bare instrumental (берегом) can sound a bit more literary, or it can emphasize following the continuous, unbroken line of the route itself.

Why use the unidirectional verb идти here instead of the multidirectional ходить?

Even though walking "along a shore" might sound like wandering, идти implies they had a specific, single destination in mind. The shore was just the chosen route to get there. If they had decided to stroll up and down the beach aimlessly for fun, you would use ходить.

I noticed ночью is also in the instrumental case. Is that the same grammar rule as берегом?

They are both in the instrumental case, but for different reasons. Ночью uses the instrumental to answer "when?" (Instrumental of Time, meaning "at night" or "during the night"), whereas берегом uses it to answer "which way?" or "along what path?" (Instrumental of Route).