Questions seeking somewhere with decent weatherin the winter frequently get posted here. While you might well get some pleasant sunshine in southern Europe, you need to go further south for warm weather. That means Africa and the only African tourist destination available on a budget is the Canaries. (While the Canary Islands are politically and culturally part of Spain, a quick glance at the map will show that they actually lie off the north African coast).
http://www.tenerife-d...om/en/tenerife_en.php
Remember though that nothing is really cheap over Christmas and the New Year. Expect to pay at least as much as you would in the peak of the summer tourist season (and possibly quite a bit more).
Chris