Algunas pistas:

1. Consigue enlaces de páginas relevantes El principal criterio de Google a la hora de decidir cómo situar tu página es el número de enlaces que te apuntan, y la calidad de las páginas de partida. No todos los enlaces valen: por ejemplo, los comentarios de muchas bitácoras están configurados para que Google no siga los enlaces que contienen. Sembrar la blogosfera de comentarios apuntando a tu página no funciona.
2. Pon texto. Google lee tu página y la indexa de acuerdo con el contenido. El texto te hace visible.
3. No dejes páginas sueltas. Cuando Google llegue a tu web entrará por una de tus páginas, seguramente porque estará enlazada desde algún sitio, se la guardará, y seguirá todos los enlaces que salgan de ella. Asegúrate de que, sea cual sea el punto de entrada, se pueda llegar a todas tus páginas siguiendo enlaces.
4. No te preocupes por las palabras clave. Pon unas pocas, asegúrate de que sean relevantes, y no le des más vueltas. El texto es mucho más importante.
5. No tengas mucha prisa. Especialmente si tu dominio es nuevo, Google no va a correr mucho en darte pista.  Hay gente que se dedica a comprar dominios y construir redes de webs, generadas automáticamente, que se enlazan entre sí, aupándose unas a otras, para acabar vendiendo anuncios fraudulentos. Una de las formas de luchar contra esto es esperar de las páginas una cierta solera. Pero si páginas que la tengan te enlazan subirás pronto en el escalafón.
6. Hax que tu página sea limpia y legible. No pongas "Página en construcción" ni texto parpadeando, por lo que más quieras. No sé si Google se fija en eso, pero debería. Y los que sí se fijarán serán tus potenciales enlazadores.
7. No contrates optimizadores. Es fácil es que te cojan el dinero y te dejen en la miseria cibernética.
8. Cuida el contenido. Google está intentando medir la relevancia de tu página para cada una de las búsquedas a que responde. Como trabajan duro y son listos, tu mejor estrategia es asumir que lo consiguen, y que cuando tu página aparece la primera como respuesta a una búsqueda es porque era la que mejor respondía a las necesidades del que buscó. Concentrate en que tu página responda a las necesidades de alguien.

Recuerda también decirle a Google que tu web existe. Más información en Google mismo (pdf).