Because this is a phenomenon that we have never experienced, we have no 'common sense' to understand it intuitively. Like the famous Twin Paradox in special relativity, the stretching of space in general relativity seems very weird indeed, and our minds refuse to accept this process. But every indication from observational cosmology indicates that just such a process occurs. General relativity provides the framework with which we can begin to understand, or accept, how it works.
The simplest answer is that the space between galaxies 'dilates' and does not come from anywhere. Another way to think about it is to imagine the universe as a kind of watermellon. When slice it along its major axis, we can marvel at how the cross sections of each slice begin from a small wafer, expand to a maximum area and then diminish in size as we reach the other end. General relativity says that the universe is a 4-dimensional object which we insist on slicing one time step at a time. At each time step, the volume of space increases, but in some sense, this space...like the bulk of the watermellon, has always been there. In each slice, the space does not 'come' from anywhere, it is just revealed to us a moment at a time like the slices of the watermellon.
This is how I think about the way in which space seems to appear out of nothingness.