How does cross-validation work exactly? I'm having a hard time figuring out how exactly cross validation works in practice: 
To do K-fold cross validation on a data set, you divide your data into K sets. Then for each fold $i$, $1 \leq i \leq K$, you fit a model $M_i$, for which you get an out of sample error $MSE_i$. 
Now you have a cross validation error: 
$CV = \frac{1}{K}\sum{MSE_i} $
You repeat this process for different sets of hyper-parameters, chosen using grid search, or Bayesian optimization, or some other suitable method, and go with the set of hyper-parameters that give you the lowest $CV$. 
So far it is clear. 
My understanding is: the models $M_i$ will have the same hyper-parameters, but they won't have the same fitted parameters (coefficients in a linear model, weights in a neural network, etc...).  
So which model from the $M_i$ models do you actually go with? 
Or is it the case that once you have chosen you hyper-parameters using CV, you then refit a new model using the entire test data set? If this is the case, isn't there a chance that the new model performs worse than all of the $M_i$. 
 A: You are mixing up things a little. It is one thing to perform K-fold cross-validation, which is simply a procedure aimed at better assessing how a model will generalize on an independent data set.
Now, if you want to tune/optimize the hyper-parameters of a model, you can do it in a variety of ways. Usually, you establish a metric and compare how the model perform considering that metric when set with different hyperparameters.
In your example, just as you suggested, once you determine that a set of hyperparameters optimize a K-fold cross-validation procedure, you use those hyperparameters to train the model on the full training dataset, and not the folds from the cross-validation procedure.
Wiki states quiet clearly the role of hyperparameters:

A hyperparameter is a parameter whose value is used to control the
  learning process. By contrast, the values of other parameters
  (typically node weights) are learned.

So, answering your question: you do not 'go with' any of the model parameters obtained while tuning the hyperparamters or performing cross-validation, but rather with the parameters you'll obtain after training the model with the optimal hyper-parameters.
