Yo lo haria de la siguiente manera:
Código PHP:
<?php
//conexion a la bd, blah blah blah
//digamos que nuestra variable categoria es $row['categoria'];
while($row = mysql_fetch_assoc($query)
{
if($categoria_anterior != $row['categoria']) {
//imprimo el nombre de la categoria
}
//imprimo las subcategorias
//y hago mi variable categoria_anterior = $row['categoria'] antes de pasar a la proxima iteracion del bucle
$categoria_anterior = $row['categoria'];
}
?>
NOTA*: Ese codigo funciona siempre y cuando estes ordenando tu consulta por CATEGORIAS, de lo contrario no funcionara correctamente.