Which leads me to my question, does cross-validation actually prevent over-fitting?
This is a common misconception, as cross-validation helps you prevent another type of overfitting than what you have in mind: it helps you not overfit on the validation set.
To better explain this you'll first need to see what's the problem with using a typical holdout strategy.
Problems with a typical hold-out strategy.
Suppose you make a standard train/val/test split. What you typically want to do is to train your model on the training set and use the validation set for hyperparameter optimization. This means that you train multiple models with different values for their hyperparameters and evaluate each on the validation set. Finally, you select the best and evaluate it one last time on the test set.
The problem with this strategy is that if you train the model for a large number of times and fine-tune the hyperparameters on the validation set, there is a chance that you have overfit the values of the hyperparameters on the validation set. This means that the hyperparameters will achieve the best results on the validation set but won't generalize well (thy are optimal just for the validation set). This happens because, through their fine-tuning, you have actually bled information about the validation set to your model.
How cross-validation counters this
Through the use of cross-validation it makes it much more difficult to overfit on the validation set. This time, instead of $1$, you have $k$ completely different validation sets, which makes it much harder for you to find hyperparameter values that are fine-tuned for the validation sets. This in turn helps the models generalize better.
Suppose you have a dataset with $1000$ samples. A typical hold-out strategy would be a 50/25/25 split which would produce a training set of $500$ samples, a validation set of $250$ samples and a test set of $250$ samples. Through optimizing your hyperparameters on the validation set you are essentially trying to score the best on those $250$ samples. It isn't very hard to identify values that lead to a better result on this small number of samples.
If we used cross-validation (e.g. $k=5$), on the other hand, we'd have $5$ completely different validation sets (each containing $150$ samples) and $5$ slightly different validation sets. Now you'd have to fine-tune the hyperparameters so that $5$ models trained on these slightly different training sets score the best on those $5$ separate validation sets. This is much harder to do in practice and usually the hyperparameter values identified through this process generalize well.
When I tell them afterward they should only use that split to report the error and that they should retrain the model on the entire dataset they tell me of their worries of this leading to over-fitting.
Note that in both strategies (holdout and cross-validation) I also had a test set. This is done because you always need an unbiased estimate of the model's performance and cross-validation evaluation isn't 100% unbiased (because it too is part of the hyperparameter optimization loop).
So you are correct that even if you are using cross-validation you always should have a test set