The normal force acting on the incline by the block does do work, but the normal force acting on the block by the incline does negative work, and the total work done by all normal forces in the system is zero (edit: see below for proof).
Therefore, the normal force can be considered a "constraint force", i.e. a force that does no work and is neither conservative nor non-conservative.
The work vanishes only when looking at all the normal forces in the system, since the normal force acts here as a mediating force, transferring the gravitational force from the block to the incline.
This example may be confusing since there are additional forces in different directions, consider the simpler setting of a force pushing two blocks on a horizontal plane:
Here the left block applies a normal force to the right block and vice versa, and again the total work done by the two normal forces cancels, since the normal force mediates the pushing force between the left block and the right block.
Another interesting example is the tension force of a string holding two weights over a pulley:
In this system the string pulls the lighter mass and does work on it, but it does negative work on the heavier mass and so the total work the tension forces do is zero. The string acts as a mediator that transfers the gravitational force between the two blocks.
Edit - corrected proof (credit to @DSinghvi for pointing out the error in the previous version of the proof in the comment below):
Here's how we can see the work done by the two normal forces cancel (and this proof can be easily generalized to any other problem with normal forces):
According to Newton's second law, the force acting on the incline by the block, $\mathbf{N}_{bi}$, is equal in size and opposite in direction to the force acting on the block by the incline, $\mathbf{N}_{ib}$, i.e.:
$$
\mathbf{N}_{bi} = - \mathbf{N}_{ib}.
$$
In the axis parallel to the normal force, the incline and the block move together, so if the incline travels an infinitesimal distance of $dx$, then the block at the same time travels the same distance $dx$. The total work done by both forces while this distance is traveled cancels:
$$
N_{bi} dx = - N_{ib} dx ~~~\Rightarrow~~~ N_{bi} dx + N_{ib} dx = 0
$$
Let's draw a quick diagram to make it clear what we're talking about:
The condition for constant velocity is that the applied force $F$ and frictional forces $\mu mg$ are equal so:
$$ F = \mu mg $$
As you thought, the normal force is not equal to the applied force - well, not unless the coefficient of friction $\mu$ happens to be equal to one.
The equation relating the frictional force $F_f$ to the normal force $F_n$:
$$ F_f = \mu F_n $$
is generally called Amonton's law. However this is an effective law not a basic principle, and in practice applies only in limited conditions. Why Amonton's law is a useful approximation is discussed in Why is the equation for friction so simple? and in more detail in the paper On the origin of Amonton’s friction law by Persson et al, J. Phys.: Condens. Matter 20 (2008) 395006.
Best Answer
Normal force is a "holding back" force.
Place an apple on a table, and the table holds it up. This "holding up" force is always perpendicular, which is why it is called the normal force ("normal to" means "perpendicular to").
Any stiff surface will hold back against something that pushes on it, like this weight of an apple, and that "hold back" force is given the name normal force.
Forget about that right away! This is not true. It might be in some cases, but it is not a general rule. Never say that normal force must be $mg$. Never say that it must be anything - it depends on the situation every time.
The apple on the table has a weight $w=mg$. The table must hold back with exactly $mg$ as well to hold up the apple. This comes from Newton's 1st law (positive direction upwards): $$\sum F=0\Leftrightarrow n+(-mg) =0\Leftrightarrow n=mg$$
Now push down on top of the apple. The table must now hold back against the apple weight $w=mg$ and the pushing force $F_{push}$: $$\sum F=0\Leftrightarrow n+(-mg) +(-F_{push}) =0\Leftrightarrow n=mg+F_{push}$$
Now push on a wall. Nothing puts weight on the wall, but you give a horizontal pushing force. The wall's normal force appears to hold back, this time horizontally (positive direction outwards from the wall):
$$\sum F=0\Leftrightarrow n+(-F_{push}) =0\Leftrightarrow n=F_{push}$$
A new value of $n$ in a new situation. Doesn't have anything to do with weight.
I hope this also cleared out the signs. You are right that the weight $w=mg$ and normal force $n$ in the apple example will have opposite signs, and they also do when you put them into the first law: the weight $mg$ pulls down (negative) while $n$ holds back upwards (positive). But they are on the same side of the equal sign, so rearranging changes a sign.