Los hostings pago incluyen casi todos un servidor SMTP activado, a menos que indique otra cosa en sus caracteristicas, lo cual seria muy raro. Hay algunos hostings gratis que tambien lo ofrecen, pero esos son muy escasos debido al abuso de tales servidores en el envio de spam.
phpMailer es una libreria/clase (la verdad, ignoro la diferencia entre esas dos palabras) escrita en PHP, que te permitira enviar mails si no tienes el servidor SMTP disponible, a traves del uso de uno externo. Su uso es muy sencillo, ya que basta con incluir unas cuantas lineas en el codigo para enviar un correo. Ya no haras uso de la funcion mail, sino mas bien de una funcion de la clase, que no recuerdo bien como se llama...
Te invito a darte una vuelta por estos links:
Tutorial de PHP y MySQL: Las Clases en PHP PHPMailer - full featured email transfer class for PHP PHP en castellano. Uso de la clase PHPMailer php php5
Un saludo,
