Bon en fait ta question c’est « comment ça marche le référencement ? » 
J’essaye de faire clair et concis.
Nos amis les moteurs (google, yahoo, msn…) lancent des robots sur la toile. Ce sont simplement des programmes qui fonctionnent comme des navigateurs autonomes intelligents. Ils vont de de sites en sites puis de pages en pages afin d’en analyser le contenu. Pour bondir d’une page à l’autre ils se basent tout simplement sur les hyperliens. Quand ils analysent le contenu, ils appliquent un certain nombre de régles pour déterminer le(s) sujet(s) de la page.
Dans un premier temps, les informations « rapportées » par les robots sont stockées dans les index des moteurs de façon « assez simple ». Précision : l’index est simplement ce qui permet de faire le lien entre des mots-clefs et des pages.
Puis, toutes les n semaines, l’index est remanié intégralement en appliquant des algos plus complexes sur l’intégralité des informations (et y en a un paquet).
C’est pour cette raison que, lorsque l’on fait une première mise en ligne, ou une première optimisation pour le référencement, le résultat est très agréable : on arrive très vite dans les premières positions. Les moteurs considèrent que ce qui est « nouveau » a plus d’importance que ce qui est établi depuis un certain temps. Et puis il y a aussi le fait que la première passe d’analyse et application de règles est relativement simple (le relativement est très relatif, ce sont des algos de fous furieux :P) Mais après le remaniement de l’index (chez Google on l’appelle la Google Dance) ça peut faire redescendre… ou mieux faire arriver en pôle position.
Les règles des robots varient assez peu d’un moteur à l’autre (google, yahoo, etc.) et sont plutôt bien connues aujourd’hui. Car, il faut savoir que, bien évidemment, Google et les autres ne diffusent pas leurs règles. Donc tout ceux qui font du référencement travaillent de façon empirique. Et ce, d’autant plus que les algos évoluent.
Google a connu son grand succès grace à une idée toute conne : améliorer la pertinence de la recherche par la popularité des pages. C’est le fameux PageRank.
A l’époque où GG a démarré, les principaux moteur (Yahoo, Altavista) étaient devenus des usines à sites de cul. Ils se basaient uniquement sur le contenu en utilisant des critères relativement peu sélectifs. Donc une bête liste de mots en noir sur fond noir était prise en compte.
Google a commencé par éliminer ces méthodes. Son robot arrive sur la page, fait un pseudo rendu pour déterminer ce qui est une vraie information (visible et cohérente) et élimine tout ce qui lui semble de la « triche ».
Ensuite, pour définitivement assoir la pertinence, Google se base sur les liens qui mènent à la page en cours d’analyse. Si ils sont nombreux, et de qualité, ie. venant de sites à bon contenu et bonne popularité, alors la page gagne en popularité et monte dans les position de l’index.
Pour infos, les critères les plus courants, et les plus efficaces :
Le référencement est un sujet passionnant. Avant d’appliquer les méthodes et techniques sur mon site pro, j’ai testé sur mon site perso (histoire d’éviter de faire des conneries) et j’avoue être assez fier du résultat Essayez donc « tour d’europe à moto » dans Google et voyez qui arrive en première position B)
Je n’ai pas encore fait le tour de toutes les méthodes (cloaking, satellites), certaines étant assez risquées car considérées comme illicites par les moteurs.
EDIT :
J’en profite pour rajouter que le référencement peut même donner lieu à des compétitions/concours. Nous avons eu le concours du meilleur positionnement sur Google pour la phrase « mangeur de cigognes » et la même chose sous MSN pour « sorcier glouton ». C’est avec ce genre de concours qu’on découvre de plus en plus de subtilités dans les méthodes de référencement. D’après ce que je sais, tous les coups sont permis et c’est ainsi qu’on a pu découvrir des méthodes « d’anti-référencement » pour faire baisser les concurrents. Ca joue sur tout un tas de techniques basées sur les redirections.
Ca aussi donné lieu à des topics surréalistes sur les forums où les participants se font des échanges de « backlinks » : je fais un lien sur ton site, tu me fais un lien sur ton site, etc. Sachant que plus on a de « bons » backlinks, plus le PageRank augmente. Mais sachant aussi que de « mauvais » backlinks font descendre le PageRank. Sauf que finalement, on a découvert que le PageRank n’était pas un critère majeur dans le positionnement.
Et ainsi de suite…
Pour ceux qui veulent approfondir le sujet, je conseille http://www.webrankinfo.com, http://www.abondance.com et http://www.webmaster-hub.com
EDIT 2 :
Les référenceurs professionnels.
Dans ce domaine là, il y a beaucoup d’arnaques !
En effet, un site bien référencé est tout simplement un site conçu pour le référencement. Pour un site existant, cela signifie qu’il faut mettre les mains dans le cambouis et dans la plupart des cas : tout refaire.
La plupart du temps, ils proposent un pack forfaitaire en précisant bien qu’il n’y a aucun garantie de résultats. Après avoir payé on reçoit deux ou trois pages HTML avec du contenu vaguement optimisé. C’est mieux que rien, mais bon…
Toutefois, les référenceurs peuvent aussi faire un boulot « manuel » long et pénible en allant soumettre le site aux annuaires. Attention, je précise bien : les annuaires, pas les moteurs. Les moteurs fonctionnent par robots et la soumission ne sert quasiment plus à rien.
Les annuaires sont souvent oubliés, et à tort.
Beaucoup d’internautes passent par les annuaires de leurs FAI (free, AOL) ou ceux de portails (Yahoo, MSN, etc.) Il y a aussi les annuaires spécialisés sur un sujet donné. Donc, pour les annuaires, il y a tout un travail de veille technologique et de marketing à faire.
Y a encore d’autres choses, mais là j’ai mal aux doigts et Koh-Lanta va commencer :-
D’autres questions ? 
Antoine