Parabolic subgroups $W_I$ of Coxeter systems $(W,S)$ and their ordinary and double cosets $W / W_I$ and $W_I \backslash W / W_J$ appear in many contexts in combinatorics and Lie theory, including the geometry and topology of generalized flag varieties and the symmetry groups of regular polytopes. The set of ordinary cosets $w W_I$, for $I \subseteq S$, forms the Coxeter complex of $W$, and is well-studied. In this talk, we look at a less studied object: the set of all parabolic double cosets $W_I w W_J$ for $I, J \subseteq S$. Each double coset can be presented by many different triples $(I,w,J)$. We describe what we call the lex-minimal presentation and prove that there exists a unique such choice for each double coset. Lex-minimal presentations can be enumerated via a finite automaton depending on the Coxeter graph for $(W,S)$. In particular, we present a formula for the number of parabolic double cosets with a fixed minimal element when $W$ is the symmetric group $S_n$. In that case, parabolic subgroups are also known as Young subgroups. Our formula is almost always linear time computable in $n$, and the formula can be generalized to any Coxeter group. This is talk is based on joint work with Matjaz Konvalinka, T. Kyle Petersen, William Slofstra and Bridget Tenner.