Battery might do it, the other common problem is that your fuel pump needs time to get the fuel from your tank to the engine. In colder weather, the engine needs more fuel to start, so the pump has to work harder and push more volume. If the gas line is half empty, it will take a while of cranking over before the fuel gets to your engine. If you put the key to the acc position, the fuel pump turns on and pumps fuel. You can actually hear this on most cars. I usually leave it on acc for about 5 seconds then turn the car on, works every time.
Another thing you may want to try, is turn on your
headlights for about 10 seconds before starting the car. This "warms up" the battery, and in essence gives it more cranking power. You might want to try this stuff before you go out and buy a new battery. Good luck.