This is a well-known phenomenon called overfitting (see the Wikipedia article). Here is the intuition : the complexity of your model is going to increase with the number of states. And a more complicated model is able to explain more data than a simple one : intuitively, a simple model can only represent simple distributions, while a more complicated model can account for more complex phenomenons. So the likelihood can only increase with the complexity of the model.
But selecting a model solely based on its likelihood (i.e. choosing the more complicated model) is a bad idea, because such a model would poorly generalize. It would not be able to represent new data points that were not seen in the training set, while a simpler model could.
To compare your models, you have to:
- Either split your observations into a training set (on which your models will be trained) and a test set (on which the likelihoods of different models can be compared fairly). This procedure is called cross validation (check the name of this website !) I recommend to have a look at Andrew Ng notes on overfitting and regularization.
- Or regularize your criterion : you need to add to your likelihood a penalty term for the complexity of the model. For instance, in the Bayesian Information Criterion, a penalty term that depends on the number of free parameters in your model is added.
