As with many things, it all has to do with money. Prior to the 16th century, all of these spices were available in Europe traveling via trade routes across Asia. Chinese and Arab traders traveled overland via the Silk Road or on ships from the Red Sea across the Indian Ocean. Cinnamon, ginger, and black pepper (native to the Malabar coast of India) were all known in Europe as far back as Ancient Rome. For centuries, Venice controlled much of the flow of spices into Europe, and the wealth gained by the spice trade may have helped spark the Renaissance.
But when the Ottoman Empire wrested control of the spice trade from Europeans in 1453, things changed. European nations, spurred by improvements in naval technology, started to search for their own routes to control the lucrative spice trade. Indeed, most of the European "explorers" who ended up in the Americas were searching for a shortcut to Asia and a way to bypass the control of the Muslim Ottoman Empire and cut out the middleman altogether, ensuring massive profits.
Instead of dealing with existing trade relationships, as Asian and Arab traders had for centuries, Europeans simply took what they wanted by force. The Dutch were particularly violent as they tried to take control of the Spice Islands through genocide and enslavement. Even after the plants that produced these valuable spices were successfully propagated outside their native habitats, the plantations which grew them commercially were often owned by foreign Europeans and also used enslaved labor to produce the spices more cheaply than ever.
Like sugar and chocolate, the plantation economy allowed spices to be produced in massive quantities quite cheaply. The flavors that were once the purview only of wealth European aristocrats were, by the end of the 18th century, much more widely affordable by ordinary people. By the middle of the 19th century, ginger, cinnamon, nutmeg, mace, and cloves (along with sugar and cocoa) were positively common. Which is why foods like gingerbread cake, spice cake, and spiced pumpkin and apple pies became such indelible parts of American food history.
But why the association with fall? In European cuisine, the most expensive foods were served around special feast days, like Christmas and Twelfth Night. Fruit cakes were rich in spices, spices flavored custards and puddings, and cookies flavored with ginger, cinnamon, mace, nutmeg, and cloves were all staples of the winter holidays. As spices became less expensive over time, they were used in other applications, but their association with the holidays - and cold weather - continued.