How does the string worldsheet affect the space-time in which they live? I don't understand much about string theory and never really got much further past the Nambu-Goto action and very basic supersymmetry (SUSY) lectures in my undergraduate courses, but the only thing that stuck is that the string worldsheet lives in space-time.
So, if strings are allowed to interact only by string exchange (which amounts just to changing the genus of the worldsheet, that still keeps living in space-time), how do we go from that state of things where we have actions (that is, Polyakov) that depend on the metric properties of the worldsheet, and describe how the worldsheet evolve inside space-time as a fixed background, to strings-exchange-things-that-curve-spacetime-itself, understanding spacetime the very space those strings live within.
If strings are allowed to interact only via string exchange, does it mean that...


*

*strings are connected topologically to the space-time via strings? That would be weird, a two-dimensional surface connected to a four-dimensional one, but I guess it would be logically possible. But that suggests that strings basically live outside space-time and only touch it through its boundaries, so closed strings are out of this picture

*space-time is itself made of interacting strings? that would not make much sense to me. How would that preserve the traditional Lorentz invariance? Besides, string theory assumes the Lorentz invariance is exact

*strings have a mass density and just behave as classical general-relativity energy-momentum stress tensor densities? That would make sense, but then that would be openly cheating, since that would not explain how strings create gravity, since gravity would be added ad-hoc

*I'm out of options. How can strings interact with the space-time manifold?

Edit 
Thanks for the existing answers, but what I want, or what I was hoping is, if there is some diagrammatic/visual insight into the connection mentioned in the answers, say, the one from flat spacetime with graviton strings propagating that turns into an equivalent curved spacetime.
 A: The strings do not attach to the space-time manifold, they move around on it as a background. Option 1 is not right.
Option 2 is more like it, except that you are assuming that string theory as it is formulated in the string way builds up space-time from something more fundamental. This is not exactly true in the Polyakov formulation or in any of the string formulations (even string field theory). The string theory doesn't tell you how to build space-time from scratch, it is only designed to complete the positivist program of physics. It answers the question "if I throw a finite number of objects together at any given energy and momentum, what comes out?" This doesn't include every question of physics, since we can ask what happens to the universe as a whole, or ask what happens in when there are infinitely many particles around constantly scattering, but it's close enough for practical purposes, in that the answer to this question informs you of the right way to make a theory of everything too, but it requires further insight. The 1980s string theory formulations are essnetially incomplete in a greater way than the more modern formulations.
The only thing 1980s string theory really answers (within the domain of validity of perturbation theory, which unfortunately doesn't include strong gravity, like neutral black hole formation and evaporation) is what happens in a spacetime that is already asymptotically given to you, when you add a few perturbing strings coming in from infinity. It then tells you how these extra strings scatter, that is what comes out. The result is by doing the string perturbation theory on the background, and it is completely specified within string perturbation theory by the theory itself.
Option 3 is sort of the right qualitative picture, but I imagine you mean it as strings interacting with a quantum gravity field which is different from the strings, strings that deform space and then move in the deformed space. This is not correct, because the deformation is part of the string theory itself, the string excitations themselves include deformations of space-time.
This is the main point: if you start with the Polyakov action on a given background
$$ S = \int g_{\mu\nu} \partial_\alpha X^\mu \partial_\beta X^\nu h^{\alpha\beta} \sqrt{h} $$
Then you change the background infinitesimally, $g\rightarrow g+\delta g$, this has the effect of adding an infinitesimal perturbation to the action:
$$ \delta S = \int \delta g \partial X \partial X $$
with the obvious contractions. When you expand this out to lowest order, you see that the change in background is given by a superposition of insertion of vertex operators on the worldsheet at different propagation positions, and these insertions in the path-integral have the form
$$ \partial X^\nu \partial X^\mu$$
These vertex operators are space-time symmetric tensors, and these are the ones that create an on-shell graviton (when you smear them properly to put them on shell). So the changing background can be achieved in two identical ways in string theory:


*

*You can change the background metric explicitly

*You can keep the original background, and add a coherent superposition of gravitons as incoming states to the scattering which reproduce the infinitesimal change in background.


The fact that any operator deforming the world-sheet shows up as an on-shell particle in the theory, this is the operator state correspondence in string theory, tells you that every deformation of the background that can be long-range and slow deformation shows up as an allowed massless on-shell particle, which can coherently superpose to make this slow background change. Further, if you just do an infinitesimal coordinate transformation, the abstract path-integral for the string is unchanged, so these graviton vertex operators have to have the property that coordinate gravitons don't scatter, they don't exist as on-shell particles.
The reason this isn't quite "bulding space-time out of strings" is because the analysis is for infinitesimal deformations, it tells you how a change in background shows up perturbatively in terms of extra gravitons on that background. It doesn't tell you how the finite metric in space-time was built up out of a coherent condensation of strings. The question itself makes no sense within this formulation, because it is not fully self-consistent, it's only an S-matrix perturbative expansion. This is why the insights of the 1990s were so important.
But this is the way string theory includes the coordinate invariance of General Relativity. It is covered in detail in chapter 2 of Green Schwarz and Witten. The Ward identity was discovered by Yoneya, followed closely by Scherk and Schwarz.
The point is that the graviton is a string mode, a perturbation of the background is equivalent to a coherent superposition of gravitons, and graviton exchange in the theory includes the gravitational force you expect without adding anything by hand (you can't--- the theory doesn't admit any external deformations, since the world-sheet operator algebra determines the spectrum of the theory).
In the new formulations, AdS/CFT and matrix theory and related ideas, you can build up string theory spacetimes from various limits in such a way that you don't depend on perturbation theory, rather you depend on the asymptotic background being fixed during the process (so if it starts out flat, it stays mostly flat, if it starts out AdS, it stays AdS). This allows you to get a complete answer to the question of scattering on certain fixed backgrounds, and get different pictures of the same string-theory spectrum in terms of superficially completely unrelated gauge fields or matrix-models.
But you asked in the Polyakov string picture, and this is only consistent for small deformations away from a fixed background that satisfies the string equations of motion for the classical background.
A: For another (brief) exposition, David Tong in his string notes makes this statement

A spacetime geometry is
  made of a coherent collection of gravitons, just as the electric and magnetic fields in a
  laser are made from a collection of photons. The short distance structure of spacetime
  is governed – after Fourier transform – by high momentum gravitons.

Then in section 7 of that reference, he demonstrates how, by insertion of the appropriate (coherent) combination of stringy graviton vertex operators in the path integral, the metric is effectively transformed from a flat one to a perturbation about flat space.
A: I'm not going to attempt a detailed answer, but the basic idea is this:  When computing observables in string theory, one gets the same values from making very small & rather singular changes in the background fields (like the spacetime metric) as one does from inserting additional strings into the computation in the correct way.  So, for example (Polchinski, vol 1, section 3.7), if you have a bunch of strings in flat spacetime, and one of them looks like a graviton, you can forget about that string, and just make an infinitesimal change in the spacetime metric.  This has been checked by hand in a very large number of possibly misleading special cases.
A: One way to think of string theories, is to think of them as a generalization of (Riemannian?) manifolds. That view is for example put forward by Graeme Segal and generally speaking, if string theory gives a consistent theory of quantum gravity one would expect that a non-perturbative formulation does not include a "background". So one approach is to give an axiomatic formulation in much the same way as it has been done for conformal field theories or toppological quantum field theories. 
As far as I know there do not exist satisfactory background free descriptions of string theory. One thing one can do is to consider open strings with dirichlet boundary conditions in some directions, this corresponds to the string ends being fixed to some lower dimensional D-brane (in first approximation one can think of them as submanifolds), then one can compute that there should be some momentum transfer from the string to that membrane. I think such a calculation can be found in the second(?) volume of Polchinski. A maybe more advanced reference are for example his Notes on D-Branes. There he uses $T$-Duality to calculate the effect of the exchange of a closed string between two branes. This was of course only the starting point. 
So I guess one answer is that besides Strings, string theory is really also a theory of higher dimensional objects called branes.
They come in various flavors, can carry charges and their intersections and relative position contribute to the determination of the low-energy effective theory (So they are part of "String Phenomenology") Since some of the extra-dimensions have to be compact they can also get tangled or confined in those compact manifolds. This then leads to interesting descriptions of them in terms of fairly sophisticated algebraic geometry.
A lot of those considerations are essentially semiclassical. I think it is fair to say, that what  could be called "stringy geometry" is still unknown.
A: You could try to start not from string theory but from relativity itself, and ask about the meaning of the Riemann curvature tensor in an arbitrary number of dimensions. Esencialy is a bunch of surfaces and then it is unsurprising that string theory can detect it.
It could be also useful to try to look at the string as a 1-brane and ask generically to what kind of tensors should a n-brane couple. I am thinking here in the relationship between the 2-brane and the antisymmetric tensor of three indexes which complements the graviton in sugra.
