I will travel in Turkey in Nov/Dec 2015. I will take the train from Istanbul to the far east of Turkey. As far as I know, Kars is the east end of the railway.
How can I go from Kars to Georgia?
Kars has quite a harsh climate. In November and December the driving conditions are not the best in that area. Moreover, if you don't want to freeze your balls off, think twice before considering options that involve walking, hitchhiking or waiting for buses or taxis in the middle of nowhere.
From Kars there is a bus to Hopa, on the shores of the Black Sea. It takes more or less 6 hours (for roughly 300 kilometers). In Summer this bus runs daily. I don't know about the Winter schedule. It may be less frequent ... From Hopa, you can take a Dolmuş or a taxi to Sarp. It's +- 10 kilometers. Cross the border and continue by taxi or minibus to Batumi.
Unless you really want to go to Kars, you don't have to. The train from Ankara to Kars (Doğu Ekspresi) also calls at Erzurum. It's a more pleasant place than Kars. Spend the night there and take an early morning bus to Hopa. There are a couple of buses every day on that route. The journey will last +- 5 hours.
Both options involve scenic rides. And you will have to spend at least one night in either Erzurum or Kars.