Li ordini nella query, quindi li stampi in quell'ordine. Dovrai rilevare le modifiche all'anno per stampare l'intestazione dell'anno:
$sql = "SELECT YEAR(FROM_UNIXTIME(timestamp)) AS YEAR,
MONTHNAME(FROM_UNIXTIME(timestamp)) AS MONTH,
COUNT(*) AS TOTAL
FROM NEWS GROUP BY YEAR, MONTH ORDER BY YEAR DESC, MONTH ";
$newsdata = DataAccess::ArrayFetch($sql);
$currentYear = null;
foreach($newsdata AS $news){
if ($currentYear != $news['YEAR']){
echo '<h2>'.$news['YEAR'].'<h2>';
$currentYear = $news['YEAR'];
}
echo '<dd>'.$news['MONTH'].'<dd><dt>'.$news['TOTAL'].'</dt>';
}