How exactly does a validation data-set work work in machine learning?
Machine learning models output some sort of function; for example, a decision tree is a series of comparisons that results in a leaf node, and that leaf node has some associated value. This decision tree predicts survival chance on the Titanic, for example:



(Image by Steven Milborrow, from Wikipedia)

This can be used exactly like the equation generated by linear regression. You feed the new data points into the model, you get predictions out, and then you compare those predictions to the actual values.

The comparison you do is applying a "cost function," and what cost function you use is determined by your application. For example, linear regression can be done with different cost functions; typically, people use "ordinary least squares" which tries to minimize mean squared error, but other possibilities exist, like minimizing the absolute value of the error. When the result is a percentage, then something like a log probability loss function is typically a better choice than mean squared difference between the actual and predicted probability.

Even k-nearest neighbors generates a function; it splits the space into regions where the k-nearest neighbors are the same set, and then has a flat value for that region. It ends up very similar to the result generated by a decision-tree based method.



There's also a terminology point here: typically, people talk about the training set and the test set, or the training set, the validation set, and the test set. The point of the validation set is different from that of the test set; the test set is used to determine out-of-sample error (that is, how much the model has overfit and what its real world error is likely to be like) whereas the validation set is used to determine what hyperparameters minimize the expected test error. 

One could fit ten different models on 80% of the data, determine which one has the lowest error on another 10% of the data, and then finally estimate real-world error on the last 10% of the data.