'na brzegu rzeka' = on the bank(s) of the river.
na brzegu rzeki
You're right, also:
nad brzegiem morza
(it's generally used with for any water basin's edge, you can't use the word "krawędź" or "skraj" here)
brzeg is just another word for "krawędź", and can also be used when saying about an edge of a rectangular surface, for example "brzeg stołu" "edge of the table).
As I said before choosing between synonyms from a dictionary can be hard, you need some experience and sometimes quite a good knowledge of the language (of course there are also simple cases, when a foreign word has one translation only, but this isn't a rule)