No es para nada un tema trivial, y tus preguntas están justificadas.
Alojamiento web: es indispensable si quieres tener una web en Internet. Como entiendo que no tienes un nivel elevado, administrar tu propio servidor será imposible y por lo tanto deberás recurrir a una compañía de alojamiento o hosting. En España tienes VisualTec (creo que se llaman así ahora, antes eran VisualNetworks), o Hostgator en EEUU. Estos te proporcionarán PHP y MySQL, entre otras tecnologías y/o lenguajes.
Dominio: el dominio es el nombre con el que se accederá a tu web y podrías registrarlo por separado del alojamiento pero lo más encillo es que tu proveedor de alojamiento lo gestione por ti. Al contratar tu alojamiento debes solicitar tu nombre de dominio.
La propia web: dependerá totalmente de las exigencias, pero deberás utilizar lenguajes como XHTML y CSS para el aspecto visual, y PHP con acceso a bases de datos para la programación. Si no quisiérais o no pudiérais hacer una propia, podéis optar por un sistema como Drupal o Wordpress, ambos en PHP+MySQL, que os facilitarán las cosas, aunque no os lo darán todo hecho ya que hay que aprender a utilizarlos.
Posicionamiento en buscadores: lo que pide de aparecer primero en Google no es algo tan sencillo y no es desde luego ninguna tontería. Para esto es primordial elegir bien el dominio (corto, conciso, que contenga las palabras clave de su negocio, en tu ejemplo, gimnasioalicante.com sería una buena idea, o el nombre de su empresa u organización).
Para ir haciendo cada cosa necesitarás aprender a usar otras herramientas, como un cliente FTP, a utilizar otros sistemas, como una base de datos, y a aprender otros conceptos. Como ves no es un proceso fácil y hay que aprender muchas cosas antes de conseguir que todo salga como uno desea - para que luego vayamos menospreciando el trabajo de los que se dedican a esto.