Suppose I have a large, thin, spherical shell of matter, with a radius R0. The gravitational field of the shell is as per Newton's law outside the shell, and is zero inside the shell by symmetry.
Now let me collapse the shell to a smaller radius, R1. The act of collapse releases energy, which I can use to do work, or to generate mass according to m=E/c². The situation after the collapse differs from the situation before the collapse in that I have some new matter, and I've filled the region between R1 and R0 with a gravitational field (whereas before, the field in that region was zero). Since energy is conserved, we see that gravitational fields have a negative energy density.
Energy--and therefore mass--can always be created by filling space with gravitational fields (just as when you want more dirt, you dig a hole). This happens automatically in an expanding universe, but the expansion we see today is vanishingly small compared to the expansion that occurred during the inflationary phase. Essentially all of the matter we see in the universe was created then.