Why do normals have two directions?
As you pointed out, a normal vector is a vector perpendicular to a surface. Because a surface (more specifically, a point in a surface) is considered to be 2D, there will allways be two vectors that are perpendicular to it (actually more than two, but we are only accounting unit vectors and from these there are only two).
You can consider one of them to be positive and the other to be negative; being the positive the one to point outwards, and the negative to point inwards.
Vertices alone, by definition, don't have normals. Their normal vectors are an interpolation of the normals of the faces the vertex is connected to. Even so, Blender uses loop normals, which means a vertex has one normal vector for each loop it belongs to.

Now the inner works is quite simple, and your answer to the thread question is here: A normal vector of a triangle is calculated by normalizing the cross product of two edges from the triangle. If you understand a bit of math, you'd know the result is a vector perpendicular to those edges, and therefore perpendicular to the whole triangle. If you change the order of those edges in the cross product, you'll get the negative 'version' of the normal (using the right hand rule). This is done so, by carefully setting the order the triangle vertices are stored and used.

Now, the main reason a flipped normal will look different from the others, has to do with Normal-Light calculations. These are dependent of the dot product, and it becomes negative if the angle between the light source and the normal is greater than PI/2.