How do scientists come up with the correct Hidden Markov Model parameters and topology to use?
I'm familiar with three main approaches:


A priori. You might know that there are four base pairs to pick from, and so allow the HMM to have four states. Or you might know that English has 44 phonemes, and so have 44 states for the hidden phoneme layer in a voice recognition model.
Estimation. The number of states can often be estimated beforehand, perhaps by simple clustering on the observed features of the HMM. If the HMM transition matrix is triangular (which is often the case in failure prediction), the number of states determines the shape of the distribution of total time from the start state to the end state.
Optimization. Like you suggest, either many models are created and fit and the best model selected. One could also adapt the methodology that learns the HMM to allow the model to add or discard states as needed.