How is the evaluation setup for YouTube faces of FaceNet?
The objective function they use to train the CNN minimizes the squared L2 distance (i.e. the squared Euclidean distance) between two similar (positive) images and simultaneously maximizes the distance between two different (negative) images. 
That means, the (squared) Euclidean distance between two representations is a measure of their similarity. 
Then, recognizing a face in a new image is as simple as 1) running it through the CNN and 2) finding its nearest neighbors with a KNN algorithm.

The last paragraph was only about images - in the Youtube Faces DB, we are handling videos of different persons.
In section 5.7 of the paper, they describe how they evaluate performance:


  We use the average similarity of all pairs of the first one hundred frames that our face detector detects in each video.


So, you were partially right: they just average the independent results over video frames. Probably for performance reasons, they chose to average the first 100 frames. They do describe that increasing this to the first 1000 frames increases performance from 95.12% to 95.18%, which is not significantly more.