Sampling from a Acyclic Deterministic Finite Automaton
Some rough thoughts:

As $M$ is acyclic and deterministic, each word $w$ in $L$ determines a unique path through $M$. Therefore, at each state $q \in Q$, we weight each transition based upon the number of valid subsequent paths (this is the size of the subset of $L$ with a particular prefix). This can be done recursively, and should be linear in the number of transitions.

Then, in order to sample, we can define a function $p: Q\times\Sigma \to R$ that gets us this 'weight' of a particular transition, and use this to define the probability of moving through that transition. At the end of this, rolling a die at each transition should get a normal sample.

I've probably missed something, but it seems like a decent approach.