Note to self: don't node about Moby. You don't like that man. Focus, young grasshopper.
Before the stars existed (that would be a long time ago, when the Universe was about a thousand years old), there existed very few things made of something more complicated than helium. Getting protons and neutrons to get together and make simple atoms and well, the victory of matter over antimatter was more than we could ask for, isn't it? But well, we know that things are made of elements heavier than lithium (some of which was supposed to be 'built' at those stages).
Well then, some clouds of hydrogen and helium were attractive enough to get into a relatively small volume. This produces high pressure and temperature, conditions needed for a lot of interesting physics stuff. We are now interested in nuclear fusion, which melds light atoms to form heavier ones. So hydrogen burns to helium, and later on, helium turns into carbon and we go on, creating the heavier elements. This is interesting to us, because it's about the only reason we have to explain how elements such as iron came to exist.
So where is the We Are All Made Of Stars part? Well, humans (and most things biological) are made mostly of carbon, hydrogen, oxygen, nitrogen, etc. (even gold. There's some gold in us. All of us). You put two and two together. Sometime, somewhere, a star exploded and the little bits that got blasted away came to be you and me. We once were stars.
Note: thanks to all the msg'ers and downvoters who made me remember that I had actually studied this.