ordina la query per categoria
e crea dai risultati un array del tipo


$arrayCategoria[1][0]="nome categoria 1";
$arrayCategoria[1][1]="nome prima sottocategoria";
$arrayCategoria[1][2]="nome seconda sottocategoria";
$arrayCategoria[2][0]="nome categoria 2";
$arrayCategoria[2][1]="nome prima sottocategoria 2";
etc etc

dove ilprimoindice dell'array indica la categoria e il secondo indica la sottocategoria

e poi qui fai giare un ciclo

for ($a=0; $a<$nCategorie; $a++)
{
print $arraycategoria[$a][0];
for($b=0; $b<$nSottoCatehorie; $b++)
{
print $arraycategoria[$a][$b];

}
}

dove $nCategorie e $nSottoCatehorie sono il numero di categorie e di sottocategorie che calcoli di volta in volta