Nynorsk and Bokmål provide standards for how to write Norwegian, but not for how to speak the language. No standard of spoken Norwegian is officially sanctioned, and most Norwegians speak their own dialects in all circumstances.
Thus, unlike in many other countries, the use of any Norwegian dialect, whether it coincides with the written norms or not, is accepted as correct spoken Norwegian.
From the 16th to the 19th centuries, Danish was the standard written language of Norway. Historically, Bokmål is a Norwegianised variety of Danish, while Nynorsk is a language form based on Norwegian dialects and puristic opposition to Danish.
Norwegians are educated in both Bokmål and Nynorsk. NRK, the Norwegian broadcasting corporation, broadcasts in both Bokmål and Nynorsk, and all governmental agencies are required to support both written languages. Bokmål is used in 92% of all written publications, and Nynorsk in 8%.
Both Nynorsk and Bokmål have a great variety of optional forms and dialects.
It is entirely possible to construct entire sentences that could be either Bokmål or Nynorsk. The two variants are 99 % mutually comprehensible for people who grow up in Norway and are exposed to both (as well as a multitude of dialects) from childhood.
Nynorsk grammar is probably a little more complex than Bokmål grammar, especially because you must observe three different genders in nouns (masculine, feminine, neuter), whereas Bokmål allows the collapsing of the masculine and the feminine into a Common gender, morphologically like the traditional masculine.
Another defining trait is that Nynorsk uses more diphthongs: "Ein" versus "en", "graut" versus "grøt" and so on. Grammatically, Nynorsk relies more on verbs and active sentences like English, whereas Bokmål uses nouns more, like German.
There are other grammatical and lexical differences between the two variants, but listing them all is outside the scope of this article.
Bokmål is the more widespread variant. If you are choosing which variant to learn, learning it would probably be the better choice. However, to repeat what was said before, the two variants are mutually comprehensible, as they are the same language, after all, although if you learn one variant getting used to the other may take some time.