Given some combinatorial structure and a notion of ordering (for example, graphs with the induced subgraph ordering, or permutations and pattern containment), the notion that a class of structures is "well-quasi-ordered" (wqo) equates to the absence of an infinite antichain in the class. Put another way, in a wqo class in every infinite set of objects there exists a pair, one of which precedes the other in the ordering. The combinatorial structure of choice for this talk is the permutation, equipped with containment (which can be thought of as the natural "induced substructure" order). The notion of labeled well-quasi-order (commonly abbreviated to lwqo) is a significant strengthening of wqo, and dates back at least to Kruskal's tree theorem in 1960, although it has received little attention in the realm of permutations before now. As the name suggests, it concerns combinatorial structures whose ground sets (for example, the vertices of a graph or the entries of a permutation) have been labeled by some ordered set L of labels, and considers the question of wqo on these labeled structures (under a refined ordering). In this talk, I will describe a recent programme to initiate the study of lwqo in the context of permutation classes. As well as being able to strengthen many earlier results about wqo to lwqo, it turns out that much more can be said about permutation classes that are lwqo over those that are simply wqo. Of particular note is that a permutation class is lwqo if and only if the corresponding class of permutation graphs is lwqo: the analogous statement for wqo remains open.