One natural notion of "random $L$-structure" is a probability measure on the space of $L$-structures with domain $\omega$ which is invariant and ergodic for the natural action of $S_{\infty}$ on this space. Such measures arise naturally as limits of sequences of finite structures which are convergent in the appropriate sense, generalizing the graph limits of Lovász and Szegedy. Further, ergodicity tells us that such a measure assigns measure 0 or 1 to any sentence of the infinitary logic $L_{\omega_1,\omega}$, so it makes sense to talk about the theory of a random structure. There is a strong dichotomy between those random structures which are almost surely isomorphic to a given countable structure and those which are not - we call the latter type properly ergodic. We provide a counting types characterization of those sentences of $L_{\omega_1,\omega}$ which admit properly ergodic random models. As corollaries, we prove an analogue of Vaught's conjecture in this context, and we show that the complete $L_{\omega_1,\omega}$-theory of any properly ergodic random structure has no models (of any cardinality).