Learn Russian: Мы гуляем по берегу реки.

The preposition по is very common for movement "along", "down", or "around" a surface. It always requires the Dative case. That is why the masculine noun берег (bank) takes the normal Dative ending -у to become по берегу.

I remember берег having a special exception ending. Is берегу irregular here?

Actually, no! For the Dative case, -у is the completely regular ending for masculine nouns. You are likely remembering the Prepositional case (used for location, like "on the bank"), where it takes a special exception ending: на берегу. Luckily, with по and the Dative case, it just follows the normal rules.

Why is the word for river written as реки here?

реки is in the Genitive case, which is used to show possession and translates to "of the river". Because the dictionary form река (river) is a feminine noun ending in -а, it changes to -и in the Genitive case.

Could we use идём instead of гуляем since both translate to "walking"?

You could, but it changes the context. The verb гулять means to walk for pleasure or take a stroll, which makes perfect sense for a scenic riverbank. If you used идём, it would sound more like you are walking along the riverbank in order to get to a specific destination.