Como exibir categoria e subcategoria?

O código abaixo deve ajudá-lo a começar. É uma "função recursiva" - uma função que chama a si mesma. Como o @Fake51 acabou de mencionar, não é muito eficiente, mas deve funcionar.

Você precisará de algum CSS para estruturar a lista que produziu.

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();

Edit:Como ainda não houve resposta aceita, aqui está meu código modificado para fazer tudo com uma única consulta SQL que deve ser muito mais eficiente, embora um pouco mais confusa potencialmente. Veja como fica para você.

//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);