First of all, the soft SUSY-breaking terms are just an "effective" description that replaces lots of qualitative, unknown physics by 100+ parameters for the known physics. At the end, one wants to construct a full theory. For example (an important example), if the full theory is a stabilized string theory compactification, there aren't any undetermined parameters left: everything is calculable, including the value of the superpartner masses and the rest of the 100+ soft SUSY breaking coefficients. The same holds for a complete model in quantum field theory.
Now, in this full theory, it's still true that SUSY is spontaneously broken; in the description with the soft SUSY breaking terms, SUSY is really "explicitly broken" by these soft SUSY-breaking terms. This explicit breaking is just required to be "soft", i.e. not influencing short-distance SUSY cancellations e.g. to the Higgs mass. The soft SUSY breaking terms are exactly the explicit SUSY-breaking terms that you may potentially produce out of a spontaneous SUSY breaking mechanism by additional physics if you neglect this additional physics.
Another fact to realize is that the fields of the MSSM aren't enough to break SUSY. One may go through the possibilities. A typical SUSY breaking will assign a nonzero vev to an appropriate field but there's no appropriate field in the MSSM that could be the primary source of SUSY breaking. So one is de facto required to add additional fields beyond the MSSM and they're the primary causes of SUSY breaking – their vev etc. Once SUSY is strongly broken in phenomena involving these new fields, it gets broken everywhere: the breaking is "mediated" to the MSSM (=visible sector), too.
Where does the hidden sector come from? You could ask the same question about the MSSM fields, too. Where do they come from? The hidden sector is just another collection of fields. In quantum field theory, one just has to add all the fields manually. MSSM isn't a "minimum field theory" in any sense we understand, and MSSM plus hidden sector isn't either, so there's really no difference. We may extend the MSSM to a bigger GUT-like model by bigger symmetries; but we won't encounter too many candidates for the primordial SUSY breaking. The hidden sector needed to break SUSY is typically completely new and unrelated to symmetries to the visible sector.
In string/M-theory, one may get a more non-vacuous answer to such questions because string theory predicts not only the exact values of all the parameters; for a particular compactification, it also predicts the exact field content. So one may say that the MSSM fields and the other fields come from "somewhere", literally, e.g. from some particular modes of stringy fields that propagate either in the whole spacetime or at some smaller locus of the extra dimensions or on some branes that are localized in the extra dimensions, and so on.
Just to mention a visually simple example, heterotic M-theory by Hořava and Witten represents the whole world as $M^4\times CY_3 \times I^1$ where $M^4$ is the Minkowski space we know, $CY_3$ is a six-real-dimensional manifold (Calabi-Yau) with the 6 extra dimensions, and $I^1$ is a line interval. In total, one has 11 dimensions. The line interval has two boundaries, each of which is occupied by an $E_8$ gauge supermultiplet. One of them gives rise, after breaking of GUT-like symmetries, to the MSSM; the other boundary contains additional gauginos from another $E_8$ group. Gaugino condensation of these other gauginos, a hidden sector, may be the source of SUSY breaking that gets communicated to our boundary, i.e. the other $E_8$.
The different mechanisms of SUSY breaking are really classified according to the method of mediation to the MSSM. So you hear terms like gauge-mediated, gravity-mediated, anomaly-mediated, and so on. Historically, people would be excited about gauge mediation (mSUGRA is a model that is similar to it) and they said lots of things why they saw it was the best one. The generic gauge-mediated models with all light superpartners, which people considered natural in them, are mostly ruled out by the LHC data by now. For various reasons, things like the anomaly-mediated SUSY breaking were gradually becoming preferred in recent year or so and the likely 125 GeV Higgs is another reason to think that those could be the preferred scenarios.
This is a very technical subject whose details are inappropriate for a single answer at this server, I think. Pick some review of SUSY breaking, e.g. this one:
This does focus on anomaly-mediated breaking as well, something that made it relatively ahead of time and that could turn out to be relevant.