¿Cómo mostrar la categoría y la subcategoría?

El siguiente código debería ayudarlo a comenzar. Es una "función recursiva", una función que se llama a sí misma. Como acaba de mencionar @Fake51, no es muy eficiente, pero debería funcionar.

Necesitará algo de CSS para estructurar la lista que ha producido.

function showItems($parent = 0) {
    $q = "SELECT id, name FROM category WHERE parent_id = $parent";
    $q = mysql_query($q);
    if(mysql_num_rows($q)) {
        echo "<ul>";
        while($r = mysql_fetch_row($q)) {
            echo "<li>";
            echo "<a href=\"page.php?id=".$r[0]."\">".htmlentities($r[1])."</a>";
            showItems($r[0]);
            echo "</li>"\n;
        }
        echo "</ul>\n";
    }
}
showItems();

Editar:dado que todavía no ha habido una respuesta aceptada, aquí está mi código modificado para hacerlo todo con una sola consulta SQL que debería ser mucho más eficiente, aunque potencialmente un poco más confuso. Mira cómo te va.

//Recursive function to show menu items from a passed in array
function showItems(&$menu, $parent = 0) {
    if(is_array($menu[$parent]) && sizeof($menu[$parent])) {
        echo "<ul>";
        foreach($menu[$parent] as $num=>$name) {
            echo "<li>";
            echo "<a href=\"page.php?id=".$num."\">".htmlentities($name)."</a>";
            showItems($menu, $num);
            echo "</li>\n";
        }
        echo "</ul>\n";
    }
}

//Create a multi-dimensional array of ALL menu items, separated by parent
$menu = array();
$q = "SELECT id, name, parent_id FROM category ORDER BY order";
$q = mysql_query($q);
while($r = mysql_fetch_row($q)) {
    $menu[$r[2]][$r[0]] = $r[1];
}

//Call the function
showItems($menu);