Model selection based on observed data sequences is used to decide between different model structures within the class of multinomial, Markov, and hidden Markov models. In a unified Bayesian treatment, we derive posterior probabilities for different model structures without assuming prior knowledge of transition probabilities. We emphasize the following tests: 1) Given a particular data sequence of n outcomes, is each state equally likely? 2) Do the data support an independent model, or is a Markov model a more plausible description? 3) Are two data sequences generated from a) the same Markov model? b) the same hidden Markov model? For Markov models and independent multinomial models, all results are exact. For hidden Markov models, the exact solution is computationally prohibitive, and instead, an approximate solution is proposed