Given an unordered countable structure, when is a presentation of it algorithmically random? Computable invariant measures concentrated on the isomorphism class of the structure lead us to one possible answer to this question. Conversely, given such an invariant measure, we may ask which measure-one set of points in the sample space is mapped to the isomorphism class, giving rise to a notion of randomness via an "almost everywhere" theorem. Even for familiar examples of invariant measures, these randomness notions are not always easy to identify; on the other hand, we show how Martin-Löf randomness (and Kurtz randomness, upon broadening "isomorphism class" to "models of a theory") can be recovered in this way. We will describe several open questions about the notions of randomness characterizable in this setting. Joint work with Nate Ackerman.