Наименее затратный:
select * from news order by `date_pub` ASC
, где date_pub собственно дата публикации новости.
(Если новости не публиковались задним числом - можно и по id сортировать)
А далее цикл в php вида
$last_printed_month = '';
foreach ($news_list as $item) {
$curr_month = date('Y-m',$item->date_pub);
if ($curr_month!=$last_printed_month) {
echo ($last_printed_month = $curr_month);
}
echo $item->title;
}
В вашем тестовом примере ничего не написано про год, но мне кажется он нужен :)
Если хочется писать месяц именно русскими буквами - надо написать крошечную функцию которая сконвертирует порядковый номер месяца - в строку :)