In what sense is SUSY a spacetime symmetry? Clearly the SUSY anti-commutation relations involve momentum, and thus the generator of translations in spacetime:
$$\{ Q_\alpha, \bar{Q}_{\dot{\beta}}  \} = 2 (\sigma^\mu)_{\alpha \dot{\beta}} P_\mu . $$
So I would say that naively SUSY has 'something to do with spacetime' since the any idiot can simply see the $ P_\mu  $ in the above as I just have. But at a deeper level is there a relation between, say, the $Q$ and $\bar{Q}$ and spacetime? Alternatively, without writing down the above relation, how can we see that SUSY has something to do with spacetime?
 A: SUSY has something to do with spacetime since its generators $Q$ carry spin angular momentum, so they change the spin of the state they act on, hence SUSY is a spacetime symmetry. And this kind of generators is called fermionic generators. (compare with the generators of gauge symmetries, which are unphysical symmetries. They don't change the spin of the state they act on, and they are called bosonic generators.) 
A: The S-matrix is a fundamental object in QFT. The 'physical symmetries' 
are those groups whose action commutes with the S-matrix. One of the motivations of SUSY, the Coleman-Mandula theorem, is a no-go result which, written in full, asserts that the largest Lie group $\mathcal{G}$ of symmetries the S-matrix possesses, has the form $\mathcal{G}=P\times H$. Here $P$ is the Poincaré group, and $H=G\times \mathbb{T}^n$ with $G$ compact, semisimple Lie group. What is importat is that a larger symmetry compatible with certain physically consistence conditions do not work, if this symmetry is a Lie group. 
Nevertheless, what Haag, Łopuszansky and Sonhius proved is that a symmetry which infinitesimally looks like a graded Lie algebra does the trick. The piece corresponding to this graded algebra is spanned by the $Q$('s) and $\bar{Q}$('s) (plural for there could be more than one supersymmetry.) 
So indeed, SUSY is related with spacetime in the sense that the generators of this symmetry are intertwined with those of the Poincaré group (=spacetime symmetries) in the relations
$$
[P_\alpha,P_\beta]=0 $$
$$
[M_{\mu\nu}, P_\rho] = -i(\eta_{\mu\rho} P_\nu - \eta_{\nu\rho} P_\mu)$$
$$ [M_{\mu\nu}, M_{\rho\sigma}] = i\left(\eta_{\mu\rho} M_{\nu\sigma} - \eta_{\mu\sigma} M_{\nu\rho} - \eta_{\nu\rho} M_{\mu\sigma} + \eta_{\nu\sigma} M_{\mu\rho}\right),$$
the one you wrote, i.e.
$$\{ Q_A, \bar{Q}_{\dot{B}}  \} = 2 (\sigma^\mu)_{A \dot{B}} P_\mu,  $$
and
$$2[Q^A,M_{\mu\nu}]=+(\sigma_{\mu\nu})^{AB}Q_{B}$$
$$2[ \bar{Q}_{\dot{A}},M_{\mu\nu}]=-(\sigma_{\mu\nu}){^{\dot{B}}_{\dot{A}}}\bar{Q}_{\dot{B}}$$
as well. This algebra is for the case of $\mathcal{N}=1$ supersymmetries. (Here the tensor $M$ is angular momentum, as you know)
You can see the SUSY generators as additional fermionic axes. These add to spacetime "fermionic" extra dimensions, if you want. 
A: The group of supersymmetry transformations is an extension of the Poincare group, which is the isomorphism group of Minkowski spacetime.  So it contains the Poincare group.  However, the supersymmetry transformations are not symmetries of Minkowski spacetime.  Rather they are the symmetries of a supermanifold which contains Minkowski spacetime.
You can think of this supermanifold, Minkowski superspace, as being a copy of Minkowski space with some extra fermionic directions.  In addition to the usual (bosonic) coordinates $x^\mu$, we also have fermionic coordinates $\theta^i$.  Ordinary translations generate translations in the usual Minkowski spacetime; $P^\mu$ moves you along the $x^\mu$ coordinate.  But supersymmetry charges generate translations in the fermionic directions; $Q^i$ moves you along $\theta^i$. 
The fermionic directions are not very big.  Supercharges square to zero, so infinitesimal translation $1 + \epsilon Q$ is precisely equal to translation $e^{\epsilon Q} = 1 + \epsilon Q + \frac{1}{2}\epsilon Q^2 + ...$.    
If you take a function $F(x,\theta)$ on Minkowski superspace -- a "superfield" and Taylor-expand in $\theta$, you'll find that the Taylor coefficients are functions on ordinary Minkowski space.  The coefficients of even powers of $\theta$ will be bosonic fields and the coefficients of odd powers will be fermionic fields.  One can often understand supersymmetry transformations relating fermionic fields and bosonic fields by identifiying these fields with the Taylor-coefficients of a superfield.  Translation in theta will mix the Taylor coefficients, giving the supersymmetry transformations.
All of this generalizes to curved manifolds.  You basically just spray "super" on everything in sight.  The canonical reference is DeWitt's Supermanifolds.
