The outside of a page is the side (edge, really) away from the binding.
Mental picture: This makes more sense if you picture a book being opened and laid flat. Now the binding is in the middle, the innermost part of the object before you. The left and right extremities are the outer parts of the book: the unbound edges of the pages.
So what is the person doing? The individual might not be literally running their finger down the edge of the page (oww, papercut!), but running it along the part of the page near this outer edge: the margin, where there's no text printed. Running a finger down the page is a way to keep track of where you are looking in a long list, and keeping your finger to the outside avoids obscuring the text and avoids smudging the ink (if the phone book is anything like newspaper print, that's a serious risk).
Caution: The phrase "outside of the page" is not an everyday idiom (not where I'm from, anyway), and I don't have any sources to back this up. This is only what I, a native speaker, immediately interpret "outside of the page" to mean. It is different to what the image in the video shows, but I am inclined to trust my judgement more than a picture which may not be specifically meant to illustrate the exact words.