From reading the paper up to page 2, it appears the weights of volume are stored at the corners of the grid instead of being the weight of the cube itself as normal Marching Cubes style algorithms prefer. These corner weights define a point between along the edge between 2 corners where there is a sign change from corner to corner.. Edges with sign changes also store a normal for the edge which are the angled line in your 2D representation in the OP. That normal information is defined during the creation of the volume (by whatever editing tool or procedural volume creation method is being used), not after the isosurface is generated as would be expected by a Marching Cubes style algorithm. This normal data "states" that the line/surface passing through the point must have the predefined normal value. In cases where Marching Cubes would bend the line at that point to mate up with another point on an adjacent edge, Extended Marching Cubes and Dual Contouring both extend the line/surface out until it intersects with the line/surface passing through the point on the adjacent edge that has a different normal value. This allows creating sharp corners from the volume data where basic Marching Cubes algorithms would round off the surface somewhat. I'm not quite understanding how QEFs (quadratic error functions) play into this except that it seems they make it easier to compute the extended point within a cube where a corner will be located.
Note that I've been talking about lines and edges here in the 2D sense as depicted by the representation in the OP.. I would have to do some more reading and thinking to extend this to 3D for volumetric mesh generation.
To address the 2nd half of your question about how to generate the normals, and thinking from a noise driven procedural point of view, it seems like you would fill your volume with noise data then look for edges with sign changes, then examine the 4 cubes that share the edge to figure out where what triangles are going to be generated, and compute the vertex normal like you would for any other intersection of multiple triangles, taking the average of the normals for each triangle that shares the vertex. This is very speculative on my part as the paper deals mostly with CSG operations and volumes generated from scan-converted meshes, both of which have well defined normals on the surfaces.
I hope at least the 1st part of this answer addresses the differences in how the weight data is represented and used in a manner quite different from basic Marching Cubes, and why the normal data has to be created fairly early on in the volume generation process, where with basic marching cubes normals are typically created as a last stage in the mesh generation process.