Soap can be made in several ways, but the very first soap was probably made by accident when some ash fell into a pot of animal fat being heated. Ash from some woods has a high lye (sodium hydroxide) content and would have reacted with the fat to form soap.
Most animal fats are triglycerides, that is three (tri) long non-polar chains, linked at one end. It looks like this:
Three dimensionally, it looks like this:
In this rendering, the carbons are blue, the hydrogens are white and the oxygens are red.
When this is heated with sodium hydroxide the chains are broken apart and each end is left with a negative charge (in this case an acid). It looks like this:
or, three dimensionally, this:
The red oxygen atoms have a negative charge, and that end is attracted to water. The long chain of carbons and hydrogens is non-polar and is not very attracted to water, but mixes easily with non-polar molecules like grease.
This ability to mix with both polar water and non-polar things is what makes soap so useful for cleaning.
Soap also mixes with water in a very particular way called micelle formation.