Hola,
Lo que tienes que hacer es AGRUPAR las subcategorias en funcion de su categoria. Basicamente hay dos formas de hacerlo:
1.- Lees solo las subcategorias de UNA SOLA categoria y los muestras. Lo repites para cada categoria
2.- Lees todas las subcategorias AGRUPADAS por categoria y vas mostrandolas una a una. Cuando detectas que has cambiado de categoria muestras un codigo HTML para separarlas y continuas.
Espero haber sido de ayuda.
PD: El codigo para hacer cualquiera de las dos opciones se puede sacar con ayuda de
www.mysql.com y
www.php.net