El borde no está animado, sino un pseudo-elemento :before ubicado con posicionamiento absoluto. Solo tienes que añadirle a tus enlaces la propiedad position: relative y luego crear el pseudo-elemento a:before con width 0 y left 50% para que no se vea y quede al medio, le das un height de 2px, le pones el color de fondo y le añades el transition a la velocidad que gustes, en tu página de ejemplo le dan .25s ease-in.
Al hacer hover sobre cada enlace (a:hover:before) le das un width de 100% y left 0.
