Most people mistakenly think that the Pencil tool and the Brush tool accomplish the same thing in MS Paint: freehand drawing.
Both tools allow you to draw freehand with lines of varying size, but there are several differences between the Brush tool and the Pencil tool:
Difference #1
The Pencil tool allows you to hold down SHIFT while drawing to "lock" your line into a perfect horizontal, vertical or diagonal. The Brush tool does not allow this option.
Difference #2
The Brush tool allows you to change drawing tips. By changing drawing tips, you can use the Brush tool to draw in the style of a marker, spray paint can, or ink pen.
Difference #3
The Pencil tool draws in a discrete manner while the Brush tool draws in a continuous manner. A line drawn with the Pencil tool will only contain fully colored pixels. A line drawn with the Brush tool will have a slightly "blurry" edge.