I've posted my question in another site, where I also didn't receive the answer I was looking for. I answered my own question there and I decided to answer my own question here as well: In the case of a linear chain HCRF, the hidden state sequences are calculated in exactly the same way as in hidden Markov models.
The HCRF formulation using maximal cliques generalizes much of the structure of a general hidden Markov classifier. Hidden Markov classifiers are generally constructed by considering priors over each possible model and estimating the class label by computing its posterior probabilities. If we represent each model by a clique potential function, and restrict each potential function to a single class label, we can reproduce this exact structure in a HCRF. The only difference will be that parameters in a HCRF will not be constrained to probabilities, so we can also see that all possible solutions given by Markov classifiers are just a subset of the possible solutions given by HCRFs.
By the way, the summation I was referring to in the original question is intractable to compute in its given form. Since it represents the result of the potential function over all possible paths, in the case of a linear chain, instead of trying to compute this summation directly, we can proceed by computing the probability of each state/transition occurring in the model and multiplying this probability by the results of the potential function along those states/transitions in a single pass using the sum-product algorithm.
The model also does not need to be computed using EM. Since its gradient is readily available, one can just use any off-the-shelf function optimizer to do the job. Conjugate gradient or stochastic gradient updates seems to operate better since they can deal better with violations of convexity.
Please someone correct me if I got anything wrong. The best resource I have found so far to help understand CRFs and HCRFs (which are just CRFs with latent variables) has been this tutorial by C. Sutton. I hope it could be of some help for others also having the same questions.