My feet and hands get cold before anything else when I ride my bicycle in cold weather. I also avoid buying bicycle specific clothing, preferring to use things I already have. Sometimes I buy things from the hunting section of a sporting goods department. Hunters need to stay warm in cold weather, too. My winter cycling shoes are a pair of walking shoes with leather uppers. They have more padding and are warmer than the canvas shoes I use in mild weather.
Step 1: Learn from the homeless
The homeless use newspapers to stay warm in the winter. I find four plies to be just about right. More plies do not really help.