There's a distinction here between ice formations and actual frozen waterfalls. A large percentage of the ice formations you'll see (including your 1st picture) aren't actual running waterfalls, but cliffs or steep gullies that in the summer would just appear damp and mossy. The "low" volume of water can still be enough to freeze into large formations. They will freeze over more easily than actual waterfalls because ice crystals are more likely to form in slow moving water than fast moving water (at least that's my impression).
In this situation, I believe that all that is required is for the high temperature to be below freezing for several days (up to a week) in a row, and thick ice formations will start to appear.
You'd probably want to look for north facing cliffs / gullies, or cliffs that otherwise don't get a lot of direct sunlight.
Where I live, it never gets cold enough for whole rivers or waterfalls to freeze, but it will get cold enough for visually striking ice formations (like in the first picture) to form. There's actually a (very small) community of ice climbers that will climb them. But that's 2nd hand information.
I'm not going to cut-and-paste 3rd party information, but the following link says things that are consistent with my impressions of the subject: http://www.alpineadven.com/recentandcurrent/iceformation.html