There are quite some tutorials, I'm sure, on the issue of normal mapping, but since you're here, I assume you're not satisfied with what you found.
In your case, the terrain is ussualy a Monge Patch, which is not a complicated 2D manifold to perform geometric measurments using normal differential geometry.
First, why a normal map technique?
Because the normal computed from the geometry, by averaging the face normals at a common vertex, like you described, and then computing another interpolated, per pixel normal won't allow for micro-relief lighting. The normal computed this way is "accurate" only if there's no "skin" on your geometric surface.
There are some algorithms that compute the normal map texture (the mostly blue/fuchsia RGB texture you know by now). They could rely on image processing (for example, a convolution kernel to compute the image gradients in the x and y direction and then take their cross product to come up with the 3d vector for a normal - which is quite natural for these Monge patches). You are not interested in those, since you already come with a texture.
Then how to map the normal texture correctly?
Its (uv) coordinates should coincide with your diffuse/ambient texture that you want to enhance with lighting computations. Like you said, the u could be in the x direction, the v in the y direction of a 2D rectangle that is viewed from above.
For this rectangle, there is an extrinsic normal that, in the "undeformed/unmapped" state, points out of the screen (like in the above figure). This is also a Monge patch, where the normal is piercing the screen towards your eyes, the tangent is down (assume you're not batman :) ) and the bitangent is towards the right. EXAMINE the little red dot in in both figures! This is the same dot on the texture, but when mapped, localy, in a neighbourhood around it, the texture will get stretched! It is this stretching that calls for differential geoemtry stuff: you want to see HOW the tangent and bitangent are pointing when this point lies on a Monge patch, instead of your rectangular, flat screen surface.
What does the normal map have to do with frames? Well, if for each pixel you assume the normal map is telling you that the NEW normal is not pointing in the perpendicular direction from the rectangle (the right figure!). You then store this corrected normal as a 3D vectors. For that you need 3 coordinates and.. a coordinate frame. Here's the magic! This frame is the initial (T,B,N) frame, the tangent-normal frame of that rectangle. When you map a pixel onto a Monge patch, you rotate this frame. This new frame comes as vertex attribute through the vertex shader input (i.e. your original per-vertex normal and a tangent vector). This tangent vector is also computed from the geometry, for example by using finite differencing: using the same concept you described, by approximating a directional derivative in the direction of u. Since you have these two geometry related vectors, you can compute the binormal ass their cross product.. and you have the whole frame.
Why do we need to transform that normal anyway?
As said before, this normal is not in object frame coordinates! It's in tangent space coordinates! You usually perform lighting computations in object space, so you need to get your normal in object coordinates by multiplying the vector you get using the tex2D sampling function from that normal texture BY the (T,B,N) matrix. Now you have the corrected normal and the lighting equation computations must work accordingly.
Another hidden aspect!: the computations of the tangent rely on the (uv) mapping AND on the geometry. For a vertex V having (uv) as its texture coordinate pair, you need to know what V' vertex of the surface is nearest to V and has a mapping of (u+epsilon, v). Since you're talking heightmaps, this vertex is easy to find in a natural way. The tangent can be approximated as (V' - V)/epsilon
and then normalize, but please observe that the texture coordinates and the geometry are both used in the computation of the tangent field. If you do not correlate them correctly, your normals will be rubbish in the end.