The correct construction is always :
Nos enteramos de [algo / something ]
If the "something" is a phrase constructed with a verb, then it's preceeded with "que"; and in this last case, the "de" is sometimes omitted.
Examples:
Nos enteramos de la noticia.
Nos enteramos de la muerte de Juan.
Nos enteramos de que Juan murió. (slightly less correct: Nos enteramos que Juan murió)
Regarding the examples in the original question:
In the first phrase "por las noticias" is just a complementary expression, ("por medio de las noticias", "a través de las noticias" = "via the news", "by means of the news"), it is not gramatically attached to the verb, it could be put inside commas, or parentheses:
Nos enteramos, por las noticias, que las flores valían más caras que los
años anteriores.
or even removed:
Nos enteramos (...) que las flores valían más caras que los años anteriores.
By the way: this reveals that the construction is slightly incorrect (though acceptable), it should be better "nos enteramos ... de que..."
The second phrase it's equivalent to:
Nos enteramos de la siguiente noticia: iba a hacer mucho frío.
Nos enteramos de lo siguiente: iba a hacer mucho frío.
Nos enteramos de que iba a hacer mucho frío.
The expression "la noticia" is slightly redundant here, it just emphasizes that the information was news for us.
EDITED: Regarding the added question:
me enteré de la noticia de que iba a ...
me enteré de la noticia que iba a ...
The first sentence is the correct one, although it doesn't sound very nice. The omission of "de" in the second sentece is incorrect, but it's a minor error: in common speak both forms are accepted. A nicer alternative is: "me enteré de la noticia: iba a".
Some reading material:
http://www.lapatria.com/story/salvataje-miedo-al-deque%C3%ADsmo-has-haz-barista
http://www.udistrital.edu.co/wpmu/flrodriguezh/files/2011/12/Padece-usted-de-dequefobia.pdf