Avoir
un site valide, bien structuré et qui respecte
la sémantique html.

Il faut aussi qu'il y ait des liens d'autres sites vers le tien.
C'est la base. Certains sites qui existent depuis des années et on des pages et des pages de contenu mais ne respectent pas ces règles, sont toujours introuvables dans les moteurs de recherche. Un grand nombre de sites d'établissements de l'éducation nationale, par exemple. Si on n'a pas un lien direct vers le site, il est totalement invisible sur la toile.
J'ajoute qu'il faut que les pages aient un contenu texte un minimum fourni et cohérent. Et qu'il ne faut pas hésiter à se dire "est-ce que telle expression apparait sur la page".
Par exemple (j'ai changé les termes mais l'esprit reste celui du cas original) : pour un organisme qui propose des "ateliers de musique" et qui revendique de ne pas appeler ça des "cours de musique". Je leur ai fait mettre au milieu d'un paragraphe "Nous privilégions l'expression 'atelier de musique' à 'cours de musique' car…" (suivi de leur philosophie). Ils sont remontés instantanément à sur la première page de Google sur toutes les recherches combinant simplement le nom de la ville de l'organisme et "cours de musique" qui était la recherche la plus fréquemment réalisée par les internautes. En plus c'est cet extrait précis de leur site, particulièrement travaillé, qui apparait dans l'extrait donné par Google.
Mais je précise que cela ne fonctionne que si le reste de la page et du site est en cohérence…
La longévité du site joue aussi. Un site bien structuré, complet et qui n'évolue pourtant pas, va remonter progressivement dans les résultats de Google. En fait, même dans les cas les plus aisés, il faut plusieurs mois avant de se retrouver dans les 3-4 premiers résultats (à moins d'un buzz énorme).
Certains affirment qu'avoir un site régulièrement modifié et mis à jour fait remonter dans les moteurs. Pour ce que j'ai pu en voir, c'est faux. Ça ne joue pas. Ça augment le nombre de visiteurs (c'est logique, si rien ne change on ne revient plus) mais pas l'indexation.