Partimos de la idea que tienes un proyecto creado con vue-cli3 y estas usando BootstrapVue.

Configurando Vuelidate

Lo primero que necesitamos es instalar Vuelidate para esto simplemente corre el siguiente comando en la terminal justo dentro del directorio de tu proyecto

npm install vuelidate --save  

Luego debemos configurarlo en nuestro archivo main.js agregando las siguientes lineas

import Vuelidate from 'vuelidate'  
Vue.use(Vuelidate)  

Vuelidate tiene varias formas de usarse en este caso vamos a usar mixin que es la propiedad que tiene vuejs para extender las funcionalidades propias, para esto solo debemos agregarlo dentro de los mixins mixins: [validationMixin] del componente donde queramos usarlo

import { validationMixin } from 'vuelidate'

export default {  
  name: "MyComponent",
  mixins: [validationMixin],
  data() {}
}

Usando Vuelidate

Como en este caso vamos a usarlo junto a BootstrapVue las cosas son un poco mas simples.

Supongamos que tenemos un input que debe recibir un número de celular el cual debe validar que el campo este lleno y que sea un número valido que comience por 3 y tenga 10 dígitos. Bueno para esto usaremos vuelidate.

<b-form-group  
  label-cols="3"
  label="Celular">
  <b-form-input
    v-model="form.phoneNumber"
    placeholder="3102334455"
  />
</b-form-group>  

import { validationMixin } from 'vuelidate'

export default {  
  name: "ComposeSms",
  mixins: [validationMixin],
  data() {
    return {
      form: {
        phoneNumber: '',
      }
    }
  }

Siguiente el ejemplo anterior, necesitamos crear un validador personalizado, para esto podemos usar un helper que provee vuelidate junto con un validador que ya trae listo y se llama numeric. Puedes encontrar la lista de todo los validadores que provee vuelidate aca

Ahora solo debemos importarlos por medio de la siguiente linea

import { required, numeric, helpers } from 'vuelidate/lib/validators'  

luego podemos definir un validador customizado

const isPhoneNumber = helpers.regex('numeric', /^3[0-9]{9}$/)  

Ahora configuramos el validador dentro del modelo que usa nuestro input, para esto agregamos una nueva función llamda validations la cual se incluye al cargar vuelidate como mixin.

validations: {  
    form: {
      phoneNumber: {
        required,
        isPhoneNumber
      }
    }

Por ultimo debemos agregar dos cosas, la primera será usar la propiedad state de bootstrap para resaltar el input cuando exista o no un error y utilizar el modelo que está enlazado automaticante por medio de vuelidate.

v-model="$v.form.phoneNumber.$model"  
:state="$v.form.phoneNumber.$dirty ? !$v.form.phoneNumber.$invalid : null"

Fijate que accedesmos a una propiedad llamada $invalid esta es una propiedad que crea por defecto vuelidate la cual indicara si la validación paso o no, el valor será un boolean. Ademas de esto cambiamos nuestro modelo por el que se enlaza automaticamente al definir nuestra validación (esto lo genera vuelidate), y por ultimo tenemos una condición dentro de :state usando la propiedad $dirty la cual si es false indica que el usuario no ha tocado aun este campo para lo cual asignaremos null al state evitando que se marque como error en el primer momento en que se carga nuestro formulario.

La segunda parte es agregar un componente que proveed BootstrapVue que se llama <b-form-invalid-feedback> este componente esta relacionado con el tag state que cuando toma un valor de true hace que se renderize, asi es que aca es donde pondremos nuestro mensaje de error

<b-form-invalid-feedback>  
  campo requerido, debe iniciar por 3 y contener 10 digitos
</b-form-invalid-feedback>  

Validacion fallida

Validacion exitosa

Con esto ya terminariamos la configuración y asi quedaría todo el código

<b-form-group  
  label-cols="3"
  label="Celular">
  <b-form-input
    :state="!$v.form.phoneNumber.$invalid"
    v-model="form.phoneNumber"
    placeholder="3102334455"
  />
  <b-form-invalid-feedback>
    campo requerido, debe iniciar por 3 y contener 10 digitos
  </b-form-invalid-feedback>
</b-form-group>  

import { validationMixin } from 'vuelidate'  
import { numeric, helpers } from 'vuelidate/lib/validators'

const isPhoneNumber = helpers.regex('numeric', /^3[0-9]{9}$/)

export default {  
  name: "ComposeSms",
  mixins: [validationMixin],
  data() {
    return {
      form: {
        phoneNumber: '',
      }
    }
  },
  validations: {
    form: {
      phoneNumber: {
        required,
        isPhoneNumber
      }
    }
  },