I'm learning about Ergodic Markov chains and understand that their graph topology and state dynamics can be described as irreducible and aperiodic. How can one formulate an algorithm to construct some random directed graph with these properties? Does such an algorithm already exist?
So far I have tried a function with size and density parameters creating a random adjacency matrix, then removing any cycles. However I realize there is a difference between aperiodic states of a Markov chain and acyclic digraphs, so I don't think this is the right way to start.
Removing cycles is not actually at all what you want: the more edges you have, the better it is, both for irreducibility and for aperiodicity.
The answer to your question depends a lot on the distribution you want your directed graph to have. To consider a common model, suppose that we take an $n$-vertex directed graph and include each of the $n^2$ possible edges with probability $p$.
Then, provided $np - \log n \to \infty$ as $n \to \infty$, the probability that the graph is strongly connected approaches $1$ as $n \to \infty$. (This can be found, for example, as Theorem 12.9 in Frieze and Karonski's Introduction to Random Graphs.) A Markov chain is irreducible iff the associated directed graph is strongly connected.
The reason for this threshold is that it is the point at which every vertex has in-degree and out-degree at least $1$ (which is definitely a prerequisite for strong connectivity, and turns out to be the last obstacle.) The expected out-degree of a vertex is $np$, so a vertex has out-degree $0$ with probability about $e^{-np}$ by a Poisson approximation. Then the expected number of vertices with out-degree $0$ is about $n e^{-np}$, so the probability that there are no such vertices is about $e^{-ne^{-np}}$ by a second Poisson approximation. The same estimate holds for in-degree.
By the time $p$ is large enough that the directed graph is strongly connected, it is already very likely to be aperiodic. If you allow loops, then we are very certain to have $\Omega(\log n)$ loops at this point, and even one loop guarantees aperiodicity. Even if you don't allow loops, we also expect many cycles of every length that's a small constant. In a strongly connected graph, just having two cycles whose lengths are relatively prime makes you aperiodic.