The NDFA->regex construction worked by "collapsing" a node in the NDFA. Choose a victim node. Construct a Kleene star for all "self loops." Lastly, form all triples of (incoming, self-loop, outgoing) edges; these become the labels of new edges. Now you can discard the victim node. Repeat until you're down to a single start -> goal node, and you're done (the edges just become alternations).
Surprisingly the length of a regex would vary dramatically by the choice of nodes to collapse. Finding the minimum regex was an unexpected challenge. Has anyone explored regexp minimization?
Incidentally it's not the case that Thompson and subset construction "are the basis of every lexer and regexp engine there is." It's not even true of the regexp engine inside the browser you're using now!