Usually, when talking about decision trees, were are referring to the C4.5 algorithm. That is, we build a binary decision tree, where at each node we need to make a decision where we split the data using the rule "variable < value" (if the variable is categorical, you can have an = sign).
How do know what the best split is? Simple, we test all possible combinations of variable and of value, and then choose the split which splits the data in the most egualitarian fashion (closest to 50-50).
How do we know if the data is being well split? We try to minimize metrics such as entropy or maximize metrics such as the Gini coefficient. You want to reduce the original entropy down to zero.
When do you stop? You either stop when you have a single sample in a node or when all samples have the same value. Alternatively, you can define a maximum depth for the decision tree (this is known as pre-pruning) or try to reduce your decision tree afterwards (this is known as post-pruning).
Why are decision trees so fast to create if they test all combinations of variables and values? Well, I lied to you. They don't test all combinations. The metrics used (entropy or gini) can be computed incrementally, so what the algorithms do is to sort the values for each variable, and then incrementally see whether including one more sample improves or reduces the score. But this is a technicality you need not be aware of.
Anything more? You should keep in mind that decision trees do one-ahead optimization. They do not find the global best decision tree. They are myopic. Therefore, if you think two variables are correlated, you should feature engineer a new variable that uses both.
My decision tree is highly variable? Decision trees are know to be very different if the same changes a little bit. This is why people build ensembles of decision trees like random forests by resampling the data to make them stronger. You do lose interpretability: you can no longer draw a decision tree, if you use many of them. See this question for more information on this.
Furthermore, I recommend these resources: