Were cloaks commonly used in medieval times, as depicted in Fantasy novels? When/why did they fall "out of style"?

Yes, cloaks and mantles, hooded and hoodless, were very commonly worn in Europe during the middle ages. The reason is fairly simple - the more difficult fabric is to produce, the more expensive it is; the more expensive it is, the more important it is to make the most efficient use of it. Earlier in the middle ages in Britain, up to the thirteenth century, cloaks were generally rectangular, a shape which creates the least amount of waste in cutting. Surviving records show a huge range of materials and value, from ordinary wool to fur-lined silk to Catherine of Valois's extravagant red velvet coronation cloak, which took one hundred yards of fabric to make (granted, silks were woven in widths of less than a yard at the time; today, most fabrics come in 45"-60" widths).

Layering was also an important aspect of keeping warm in this period. English men and women would wear a linen layer (the shirt/smock) which would be more frequently washed, then a cote and a surcote. Cotes were essentially loose tunics of varying lengths, belted or girdled, while surcotes were even looser. In the late middle ages, with the advent of tailoring techniques and more fitted clothing, men's and women's clothing were differentiated to a greater extent, men wearing fitted doublets and women wearing fitted kirtles as the cote layer, and both wearing tightly-fitted, buttoning cotehardies on top until the fifteenth century, when looser gowns and houppelandes came into fashion. The outer garments were not regarded as something to be put on and taken off when going out or coming like a cloak - they were full outfits along with the more fitted layers - but they served to keep the wearers warm.

I'm not sure when the cloak stopped being worn by men, but for women I would say that around 1800 a sleeved garment began to be worn as a removable outer layer more frequently than cloaks. The spencer was a short, high-waisted jacket; the pelisse and redingote were versions with long skirts. Cloaks were still worn in some contexts, such as by the poor, who could not afford to transition into this new fashion just yet; and by wealthy women going out for an evening party (it won't crush your fancy gown's sleeves like something more fitted), but the sleeved garment was seen as the ordinary choice. Then with the advent of the very loose and cloaklike kimono coat around 1905, the cloak as a necessity became obsolete, though it could still be worn for effect for a few decades.