Understanding regularization I'm currently trying to understand regularization for logistic regression.

So far, I'm not quite sure whether I really got it. Basically, the problem is that when we add an additional features to a model we might overfit the training set. This leads to an algorithm which perfectly matches the training set, but fails for future values (as it too exactly fits what has been there in the past).

So, this is why we introduce regularization. With this we decrease the impact of the features, so the model may produce an algorithm which does a (seemingly) worse job on the training set, but overall works better.

Is this correct?
That's correct. Without regularization your model would fit to an irrelevant noise present in your dataset. It means that training set will fit better but the overall predictive power will decrease. This is a good article about overfitting and regularization.

Also you can get some intuition by watching these images:
Without regularization
With regularization
You can clearly see that the shape at the 1st image has problems with prediction at the upper left corner but it perfectly fits to the training points.