¿Cómo crear un menú anidado desde MySQL con PHP?

Esto es específicamente para dos niveles de profundidad. El enfoque recomendado, en caso de ser más, es utilizar una estructura de tabla optimizada para el recorrido, como http://articles.sitepoint.com/article/hierarchical-data-database/2 (señalado en otra parte) o para obtener los datos que necesita y enviarlos a un diccionario (matriz asociativa) y consultarlos de esa manera.

<?php
    $query = <<<EOT
        SELECT
            parent.name as parent_name,
            child.name as child_name,
        FROM
            items child
        INNER JOIN
            items parent
        ON
            child.parent_id = parent.id
        ORDER BY
            parent.name
EOT;

    $result = mysql_query($query) or die('Failure!');

    echo "<ul id=\"catmenu\">";

    $last_parent = '';
    while($row = mysql_fetch_array($result)){
        // If this is a new category, start a new one
        if($last_parent != $row['parent_name']){
            // Unless this is the first item, close the last category
            if($last_parent != ''){
                echo "</ul></li>";
            }
            $last_parent = $row['parent_name'];
            echo "<li class=\"menulist\">{$row['parent_name']}<ul>";
        }
        echo "<li>{$row['child_name']}</li>";
    }

    // If we actually had items, close the "category"
    if($last_parent != ''){
        echo "</ul></li>";
    }

    echo "</ul>";

?>