Nynorsk is a constructed language. It resembles some dialects. I find it difficult to read, but I don't usually have difficulty understanding the spoken dialects. It is based almost entirely on dialects of the south-western region, and excludes as many as it includes (at least).
Bokmål is the natural development of the norwegian written language from being entirely danish a hundred and fifty years ago (when "getting an education" meant going to copenhagen and learning danish, french and latin, more or less). I find bokmål to be more natural and less constipated. Some people love nynorsk (you may sense that I have a bias against it... I totally do! ).
If you learn to read bokmål, you will be able to read danish and norwegian with ease, and you will be able to read nynorsk and swedish with more concentration and effort.
I guess it is all a question of habit. If you learn to understand the dialect around Oslo (the closest spoken dialect to the written bokmål) you will not necessarily be able to understand the dialects of Stavanger, Bergen, Nordfjordeid, Trondheim, Bodø, Tromsø, Kirkenes... but it would be easy to get hang of it if you started hearing them, because the differences are quite systematic - either specific replacements of certain phonems, or a change in the grammar (or both). Like I said: Once you start hearing them, it will just take a small amount of time to adjust to the differences.