Gracias por los consejos, al final lo he solucionado así:
Código PHP:
<?
require_once('../vars.php');
$datoslinks = mysql_query("SELECT * FROM links ORDER BY categoria, id ASC");
$categoria = "";
$catAnterior = "";
while ($link = mysql_fetch_array($datoslinks))
{
$categoria = $link['categoria'];
if( $categoria!=$catAnterior ){
print "<br />";
$catAnterior = $categoria;
print '<span style="color:lime">'.$categoria.'</span>';
}
?>