What are the strings in string theory made of? This is a follow-up to an intriguing question last year about tension in string theory.
What are the strings in string theory composed of?
I am serious. Strings made of matter are complex objects that require a highly specific form of long-chain inter-atomic bonding (mostly carbon based) that would be difficult to implement if the physics parameters of our universe were tweaked even a tiny bit. That bonding gets even more complicated when you add in elasticity. The vibration modes of a real string are the non-obvious emergent outcome of a complex interplay of mass, angular momentum, various conservation laws, and convenient linearities inherent in of our form of spacetime.
In short, a matter-based vibrating real string is the outcome of the interplay of most of the more important physics rules of our universe. Its composition -- what is is made of -- is particularly complex. Real strings are composed out of a statistically unlikely form of long-chain bonding, which in turn depend on the rather unlikely properties that emerge from highly complex multiparticle entities called atoms.
So how does string theory handle all of this? What are the strings in string theory made of, and what is it about this substance that makes string-theories simple in comparison to the emergent and non-obvious complexities required to produce string-like vibrations in real, matter-based strings?

Addendum 2012-12-28 (all new as of 2012-12-29):
OK, I'm trying to go back to my original question after some apt complaints that my addendum yesterday had morphed it into an entirely new question. But I don't want to trash the great responses that addendum produced, so I'm trying to walk the razor's edge by creating an entirely new addendum that I hope expands on the intent of my question without changing it in any fundamental way. Here goes:
The simplest answer to my question is that strings are pure mathematical abstractions, and so need no further explanation. All of the initial answers were variants of that answer. I truly did not expect that to happen!
While such answers are sincere and certainly well-intended, I suspect that most people reading my original question will find them a bit disappointing and almost certainly not terribly insightful. They will be hoping for more, and here's why.
While most of modern mathematical physics arguably is derived from materials analogies, early wave analogies tended towards placing waves within homogeneous and isotropic "water like" or "air like" media, e.g. the aether of the late 1800s.
Over time and with no small amount of insight, these early analogies were transformed into sets of equations that increasingly removed the need for physical media analogies. The history of Maxwell's equations and then SR is a gorgeous example. That one nicely demonstrates the remarkable progress of the associated physics theories away from using physical media, and towards more universal mathematical constructs. In those cases I understand immediately why the outcomes are considered "fundamental." After all, they started out with clunky material-science analogies, and then managed over time to strip away the encumbering analogies, leaving for us shiny little nuggets of pure math that to this day are gorgeous to behold.
Now in the more recent case of string theory, here's where I think the rub is for most of us who are not immersed in it on a daily basis: The very word "string" invokes the image of a vibrating entity that is a good deal more complicated and specific than some isotropic wave medium. For one thing the word string invokes (perhaps incorrectly) an image of an object localized in space. That is, the vibrations are taking place not within some isotropic field located throughout space, but within some entity located in some very specific region of space. Strings in string theory also seem to possess a rather complicated and certainly non-trivial suite materials-like properties such as length, rigidity, tension, and I'm sure others (e.g. some analog of angular momentum?).
So, again trying to keep to my original question:
Can someone explain what a string in string theory is made of in a way that provides some insight into why such an unusually object-like "medium of vibration" was selected as the basis for building all of the surrounding mathematics of string theory?
From one excellent comment (you know who you are!), I can even give an example of the kind of answer I was hoping for. Paraphrasing, the comment was this:

"Strings vibrate in ways that are immediately reminiscent of the harmonic oscillators that have proven so useful analytically in wave and quantum theory."

Now I like that style of answer a lot! For one thing, anyone who has read Feynman's section on such oscillators in his lectures will immediately get the idea. Based on that, my own understanding of the origins of strings has now shifted to something far more specific and "connectable" to historical physics, which is this:

Making tuning forks smaller and smaller has been been shown repeatedly in the history of physics to provide an exceptionally powerful analytical method for analyzing how various types of vibrations propagate and interact. So, why not take this idea to the logical limit and make space itself into what amounts to a huge field of very small, tuning-fork-like harmonic oscillators?

Now that I can at least understand as an argument for why strings "resonated" well with a lot of physicists as an interesting approach to unifying physics.

Addendum 2018-03-28: The Answer (no kidding!)
This year for the first time I submitted an essay, Fundamental as Fewer Bits, to the annual FQXi foundational questions essay contest. In the essay I propose that Kolmogorov complexity provides a more automated way, less human-biased way to apply Occam's Razor to physics theories, literally by trying to find the least-bits representation of the Kolmogorov sense of program-like data compression. (My thanks to Garrett Lisi for noticing the connection to Occam's Razor; I had not thought of my essay that way.)
The contest, which this year goes on until May 1, 2018, proved to be much more interesting and interactive than I had anticipated. In the course of looking at other essays I dove into the details of how string theory originated. I was amazed to find out that the concept has some very solid experimental data behind it... at a scale about $10^{20}$ times larger than the one at which it is now described!
As it turns out, string theory originated in some extremely interesting 1960s and 1970s experimental research on hadrons. A hadron is any particle composed of quarks, and includes both two-quark bosonic mesons and three-quark fermionic baryons such as protons, neutrons, and the more exotic $\Lambda$ particles. Being composed of quarks, all hadrons are of course bound together by the strong force, and therein likes the real, experimentally meaningful Answer to what the questions of what strings are composed of:
All real, experimentally meaningful strings are composed of the strong force.
It seems that most (perhaps all) hadrons have excited states in which their spins are augmented in increments of 2. For example, both the proton and neutron normally has a spin of $\frac{1}{2}$, but both also have higher spins states of e.g. $\frac{5}{2}=\frac{1}{2}+2$ and $\frac{9}{2}=\frac{1}{2}+4$.
These higher spins states also have higher masses. Amazingly, when all the possible states are plotted in a spin-versus-mass-squared graph, the result is beautiful set of straight lines with even spacing between the 2-spin additions. These lovely and highly unexpected lines are called Regge trajectories, and they are the true origins of string theory.
Theoretical analyses of these remarkable regularities could be explained by assuming them to be the stationary vibration modes of a string. In fact, if you think in terms of how a skip rope can have one, two, or even more loops in it when handled by an expert, you are not too far off the mark. At the time there was hope that these remarkable string-like vibration models might lead to a deeper understanding of both fundamental and composite particles. However, quantum chromodynamics (QCD) instead began to dominate, while Regge trajectories continued to pose theoretical problems. It looked like the end for hadron-level strings and string vibrations, despite the truly remarkable and still unexplained regularities seen in Regge trajectories.
Then something very strange happened, an event that to my way of thinking was one of the least rational and most bizarre events in the entire history of physics. I call it the Deep Dive. It has features that I would more typically associate with the ancient and fascinating history of religious revelation and the founding of new religions than I would with scientific analysis.
While they were not the only people involved, in 1974 physicists Scherk and Schwarz wrote a conventional looking paper, Dual Models for Non-Hadrons, with an extremely unconventional conclusion tucked away inside. The conclusion was this: Because the two-spin increments of hadron strings bore several mathematical resemblances to the proposed properties of spin-2 gravitons (the still-hypothetical quantized particles of gravity), they were in some way one and the same thing, and the concept of string vibrations should therefore be moved from out of hadrons and into the domain of quantum gravity.
This enormous leap of faith was the origin of what we now call "string theory".
There was of course a "tiny" problem, in the most literal since of the word: This abrupt leap from very real, experimentally meaningful string-like vibration modes in hadrons to gravitons plunged the needed size scales down to the experimentally inaccessible Planck foam level. This was a drop of about 20 orders of magnitude, with a comparable increase in the energy levels needed to access the proposed vibrations. Even worse, all of the severe constraints on vibration modes imposed by hadron "architectures" were instantly removed by this proposed drop, allowing the number of vibration modes of the now-abstract strings composed of a now-abstract substance (maybe mass-energy?) to explode into at least $10^{500}$ possibile vacuum states.
I explore all of this a bit more -- actually hmm, less than I just did here -- in a mini-essay attached to my FQXi essay discussion. In that mini-essay I argue that It's Time to Get Back to Real String Theory. That is, there remains to this day a very real and extraordinarily interesting data puzzle in the very existence of Regge trajectories. This is a mystery that still needs to be resolved! This data is another example of how spin is a remarkably deep and fundamental concept, one for which physics still seems to be missing some kind of critical piece or pieces.
Regarding the question "What are the strings in string theory made of?", the answer could not be any clearer: In the real, experimentally meaningful strings found back in hadron research in the 1960s and 1970s, they are a function of the strong force, constrained in interesting and limiting ways by the quarks that enable a string-like topology to exist in the first place. This is all very real, very meaningful physics.
For the Planck-level strings that were proposed essentially by revelation, that is, by a leap of faith from experimentally meaningful physics down 20 orders of magnitude to the inaccessible level of the Planck foam, based on no more than a superficial mathematical resemblance, and with utter abandonment of any of the original tight constraints on both substance (the strong force) and vibration modes (the "topologies" of mesons and baryons), the epistemological nature of the Deep Dive now also allows me to provide a more logically precise and self-consistent answer: The substance of which Planck-level strings are composed is exactly the same as the substance that angels use to bind themselves to each other while dancing on the head of a pin.
If you think that's an unfair comparison for a scientific discussion, no problem: Just state exactly what scientific experiment should be performed to prove that Planck-scale strings are not composed of the same substance that angels use bind themselves to each other while dancing on the head of a pin.
If string theory is truly science, and if the half-billion dollars of critically important research funding that has been spent on it over four decades has not been a complete waste of money, then defining a simple test to prove that Planck-level string theory is more than just an untestable religious revelation gussied up with loads of equations should be no problem at all. Right?
 A: This question from 2012, "What are the strings in string theory made of?", now has a 2018 addendum in which the author proposes (I paraphrase) that the only real strings are QCD strings made of gluons, and that the strings of string theory are unreal and a mistake. The addendum is a diatribe which departs from the original question, but I would like nonetheless to respond to it. 
It is asserted that string theory took a wrong turn when Scherk and Schwarz proposed to interpret the massless spin-2 object as a graviton, and the characteristic scale of the theory as the Planck scale rather than the QCD scale; and that this was a step away from science because now we have a theory with a googol or more ground states, unconstrained by the need to match hadron behavior. Instead, theorists should have stuck with trying to explain strong force phenomenology, and in particular the Regge trajectories which suggested strings in the first place. 
Now, initially, as is well known, strings fell out of favor once the standard model came together. So theorists of the strong interaction didn't get involved with string theory; they developed QCD, a field theory. 
Meanwhile, once string theory was reborn as a theory of everything with extra dimensions, only a literal handful of people dared to work on it. The mainstream effort to obtain a unified theory stayed with field theory. The possibilities of field theory were explored - grand unification, supersymmetry, supergravity, extra dimensions. 
So investigations into field theory had reached the point where it looked a lot like string theory anyway. And at that point the mainstream was ready to investigate string theory properly. What they found was a flood of new information. Strings resolved the formal problems of quantum gravity; they could in principle predict the couplings and the particle masses; via branes they had a multitude of connections to field theory that are still being uncovered. 
There was already a long history of interplay between field theory and string theory. 't Hooft had described the 1/N expansion of a strongly coupled field theory, in which Feynman diagrams with numerous vertices became meshlike approximations to string worldsheets. Polyakov wanted to understand flux tubes in gauge theories in terms of strings in an extra dimension. Maldacena combined these ideas in the context of superstring theory, producing his famous AdS/CFT duality. 
Sakai and Sugimoto described a string-theory setting - an intersection of two stacks of branes, in a particular geometry - which has become the standard way to mimic QCD within string theory. It does a good job of imitating the very complex spectrum of bound states that occur within QCD, and has connections to Skyrme's model, a respected non-stringy approach to the strong force. 
I mention all this to emphasize that the application of string theory to the real world is not just about Calabi-Yau spaces and supersymmetric grand unification. There is a parallel line of development which pertains much more directly to strong-force physics. 
Nonetheless, there is, empirically, more to the world than just the strong force. So it's nice that string theory can give us other things we need, like gravity and chiral fermions, as well as shedding light on the dynamics of strongly coupled field theories. 
The expectations of the mainstream unification program have been somewhat confounded by the LHC's failure, so far, to reveal anything beyond the Higgs boson. For string theory as a theory of everything, this may mean that people need to look at different vacua than the ones they are used to considering, like nonsupersymmetric ones. Maybe people should try to extend the Sakai-Sugimoto model to encompass the whole standard model, and see what happens. 
Regardless of what twists and turns lie ahead, it's something of a mistake to think of string theory as an entirely separate world of theory, so far unproven, contrasted to the realm of field theory, which is experimentally validated every day. On the contrary, you could literally write a book about the ways in which string theory has directly enriched the study of field theory. 
And given field theory's high-energy ("ultraviolet") problems, it is highly plausible that string theory is simply the framework in which field theory becomes truly well-defined. The relationship is most acutely formulated in terms of Vafa's swampland concept. The swampland is the complement to the landscape of string vacua; it consist of all those field theories which do not exist as the low-energy limit of a string vacuum. If string theory is the unique way to UV-complete a field theory, then the field theories in the landscape have a special status mathematically. 
So to sum up, although string theorists are very far from agreeing on which vacuum, or even on what type of vacuum, describes the real world; and although theorists are of course free to pursue other hypotheses (which may nonetheless turn out to be string theory in a new guise); it doesn't really make sense to say field theory good, string theory bad, let's focus on the Regge trajectories. There is a landscape of possible field theories even greater than the landscape of string vacua, and the latter landscape tells us something important about the former landscape. And it is likely that the QCD explanation of Regge trajectories will come via the application of string theory - the ten-dimensional string theory that all those millions of dollars have been spent studying - in the appropriate form. 
A: This is to complete @Dilaton 's answer.
The very basic reason theoretical physicist are entranced by string models and their extensions is because they promise to be the framework of the Theory Of Everything, the holy grail of theoretical physics.
String theories and their extensions provide for the quantization of gravity, the long standing difficulty in formulating a TOE. If there existed a competing theory with composite preons or what not,  which included the quantization of gravity in a unified manner, one would estimate the merits of each as a TOE. At the moment string theory has no competition, and strings are the fundamental entities of reality in these theories.
A: In short, string is a dislocation defect of the vacuum crystalline structure.

This by the way explains why apparent full angle around a string seems to be smaller than $2 \pi$.
A: OP wrote(v4):

[...] Strings in string theory also seem to possess a rather complicated and certainly non-trivial suite materials-like properties such as length, rigidity, tension, and I'm sure others (e.g. some analog of angular momentum?). [...]

Well, the relativistic string should not be confused with the non-relativistic material string, compare e.g. chapter 6 and 4 in Ref. 1, respectively. In contrast, the relativistic string is e.g. required to be world-sheet reparametrization-invariant, i.e. the world-sheet coordinates are no longer physical/material labels of the string, but merely unphysical gauge degree of freedom.
Moreover, in principle, all dimensionless continuous constants in string theory may be calculated from any stabilized string vacuum, see e.g. this Phys.SE answer by Lubos Motl.   
OP wrote(v1):
What are strings made of?
One answer is that it is only meaningful to answer this question if the answer has physical consequences. Popularly speaking, string theory is supposed to be the innermost Russian doll of modern physics, and there are no more dolls inside that we can explain it in terms. However, we may be able to find equivalent formulations. 
For instance, Thorn has proposed in Ref. 2 that strings are made of point-like objects that he calls string bits. More precisely, he has shown that this string bit formulation is mathematically equivalent to the light-cone formulation of string theory; first in the bosonic string and later in the superstring. The corresponding formulas are indeed quadratic a la harmonic oscillators (cf. a comment by anna v) with the twist that the "Newtonian mass" of the string bit oscillators are given by light-cone $P^+$ momentum. Thorn was inspired by fishnet Feynman diagrams (think triangularized world-sheets), which were discussed in Refs. 3 and 4. However, string bit formulation does not really answer the question What are strings made of?; it merely adds a dual description.
References:


*

*B. Zwiebach, A first course in String Theory.

*C.B. Thorn, Reformulating String Theory with the 1/N Expansion, in Sakharov Memorial Lectures in Physics, Ed. L. V. Keldysh and V. Ya. Fainberg, Nova Science Publishers Inc., Commack, New York, 1992; arXiv:hep-th/9405069.

*H.B. Nielsen and P. Olesen, Phys. Lett. 32B (1970) 203.

*B. Sakita and M.A. Virasoro, Phys. Rev. Lett. 24 (1970) 1146.
A: The question "what is xxx made of" is really asking "what can xxx be decomposed into"?
For example we know matter is made of atoms because it can be decomposed into atoms. We know atoms are made of electrons, protons and neutrons because atoms can be broken down into electrons, protons and neutrons. But electrons can't be decomposed into anything, so it's meaningless to ask what an electron is made of. We can ask what an electron's mass is, or its energy, or its spin, etc etc, but to ask what it's made from is a question that has no answer.
Exactly the same applies to a string. It is an object that has properties, but it's meaningless to ask what it's made from because it can't be broken down into anything.
A: Lenny Susskind explains that the answer to this question depends on the parameters of the theory at 1:10:50 to the end of this video.
He makes use of the fact that the question if strings are fundamental or if they are composed of something else is analogous to the question if in electrodynamics, electrons or magnetic monopols have to be considered fundamental to be able to develop a perturbation theory with Feynman diagrams.
It can be shown that magnetic charges $q$ and electric charges $e$ are related by 
$$ e\, q = 2 \pi$$
This means, that if the charge of the electron (and therefore their mass) is small, the charge of the magnetic monopoles (and their mass) is huge and vice versa. If the charge and the mass of the electron are small, the electron is considered fundamental and a converging theory (QED) can be developed because the coupling constant $e$ is small. At the same time the magnetic monopoles are heavy complicated things composed of whole bunches of photons and magnetic charges because the coupling constant $q$ is large. This regime corresponds to what we observe with QED being a weakly coupled theory and the magnetic monopoles (if they exist) being to large to be observed. Increasing the electric charge of the electron would lead to a transition to a situation, where the electons become heavy and complicated and in this case it would be more useful to consider a quantized electromagnetic theory with the ligth magnetic monopoles described as fundamental particles.
A similar relationship as described to hold for the pair of electric and magnetic charges exists in string theory between fundamental (f-) strings and D-branes. Depending on the parameters of the theory, either it is more appropriate to consider the D-branes as complicated heavy things composed of fundamental strings, or the D-branes are light and fundamental whereas strings are heavy and complicated things composed of D-branes. The technical term describing this ambiguity is S-duality.
In summary, a unique and universally valid answer to the question what strings are made of can not be given; it depends on the parameters of the theory and the context if it is more useful to consider strings or D-branes as fundamental.
A: In string theory the strings are fundamental objects and cannot be made of anything.
However, the strings of string theory, like more general extended objects --e.g., the membranes in brane theory--, can be considered to be made of more fundamental point-like objects. 
An interesting picture is given in Point-Like Structure in Strings
I would finally emphasize that the D0-branes used in Banks' matrix theory or the Thorn's bits are not the more fundamental pointlike objects. For instance, believing that universe is really made of D0-branes would be so misguided as when string theorists believed that universe was really made of strings.
A: (Please note that I am attempting to answer my own question.)
In string theory it has been implicitly hypothesized, but not rigorously proven, that the mathematical constructs used to describe the vibrations of certain of isotropic materials in simple geometric simple shapes (e.g. strings or rings) are examples of mathematical constructs so fundamental that they show up at many different levels and circumstances in physics. If this string hypothesis is true, then the vibrations of ordinary material strings are a distant echo of these far more fundamental mathematical rules.
There is a precedent for this in modern physics. When James Clerk Maxwell first integrated the knowledge of electricity and magnetism of his time into a single unified theory, he did not at first use differential equations. Instead, he intentionally built a purely mechanical rotating-cell model based on generalizations of specific properties encountered in everyday material objects.
It was not until after Maxwell had used his mechanical model to prove that light was electromagnetic radiation that he realized that all the behaviors of his model could instead be expressed using 20 quaternion-based differential equations with 20 variables, which Oliver Heaviside later compressed down to a mere four vector-based equations that are now called (not entirely accurately) "Maxwell's equations".
The situation hypothesized for string theory is roughly comparable. It also starts with a materials-based dynamic analogy, and similarly proposes that the mathematics that describe that dynamic model are expressions of some deeper and more profound mathematical model. However, it is also true that what constitutes a "fundamental" set of mathematical constructs is much less clear in string theory than it was for the far simpler domain of electromagnetism. That is in part because for string theory the analogies from materials science are extended to much higher numbers of dimensions, and because string theory postulates modes of vibration that are not accessible to direct experimentation and refinement.
A: You can derive string theory from time travel and $\mathrm{NP}$-completeness. Time travel forces nature to solve hard problems and from what we know of computational complexity, strings are needed as the primitive objects of an efficient algorithm for $\mathrm{NP}$-complete problems. All point-particle interactions in more than one dimension are damped exponentially due to jamming.
Suppose that physics takes place in a region with CTCs. (You can derive something that at least looks like quantum physics from this assumption, but that's another question.) According to a paper by Aaronson and Watrous (https://arxiv.org/abs/0808.2669) CTCs can efficiently solve $\mathrm{PSPACE}$ problems both in classical and quantum physics. Assuming the problems aren't solved by magic, there must be some polytime algorithm that solves $\mathrm{PSPACE}$ problems for time travel to be realizable.
If we narrow our attention to time travel problems whose initial values make them $\mathrm{NP}$-complete (rather than $\mathrm{PSPACE}$-complete or manifestly in $\mathrm{P}$), we can approximate the initial value problem and the evolution problem as satisfiability problems, presented as CNFs.
If we assume quantum field theory (or for that matter classical field theory in a spacetime with CTCs) has no local mechanism of solving hard problems. This likely requires the additional assumption that $\mathrm{BPP}=\mathrm{BQP}$ to show that QFT can only efficiently solve the same class of problems as classical field theory and showing that field theory has the same proof power as Resolution (see below). We can then infer that (almost) all interactions must be carried through strings. The $\mathrm{BPP}$ in $\mathrm{BPP}=\mathrm{BQP}$ also lets us use a PCP approach whereby the physically realistically task of approximating a $\mathrm{NP}$-complete problems beyond a certain threshold is just as hard.
If we look at any time slice of a time travel spacetime, the time evolution (and any interactions) will be $\mathrm{NP}$-hard. This is because a local change will, through time travel, propagate non-locally and non-causally to other regions in the time slice. This will be true even if the SAT problem is arranged on a 2-dimensional grid. (Planar SAT is $\mathrm{NP}$-complete: https://en.wikipedia.org/wiki/Planar_SAT) Only one-dimensional objects will be tractable. Actually the one-dimensional objects can have a constantly bounded thickness because bounded tree-width CNFs will still manifestly be in $\mathrm{P}$. This can be thought of a way to encode information like the boson and fermion modes of the string. (The original field data is likely encoded in the coordinate data of the strings.) For spin glasses similar intractability issues arise, however for time travel systems, nature must find a solution, so there must be long range interactions.

In proof complexity a major distinction is made between Resolution and equivalently weak proof systems and stronger proof system like Extended Resolution, Frege, and Extended Frege. Resolution is proven to require exponentially long refutations for some satisfiability problems, but stronger proof systems like Extended Resolution are known to have short proofs where Resolution does not.
Resolution uses a very simple rule for reasoning about clauses.
Resolution Step:
Given $A \lor l$ and $\lnot l \lor B$ conclude $A \lor B$, where $l$ is any literal (possibly negated variable).
For example, $(x_1 \lor \lnot x_2 \lor x_3) $ and $(\lnot x_3 \lor x_4 \lor \lnot x_5)$ implies $(x_1 \lor \lnot x_2  \lor x_4 \lor \lnot x_5)$.
Resolution can easily lead to a blow up in proof size. This is controlled by the maximum number of literals in the clause, width. There are exponential lower bounds on proofs using resolution.
Extended Resolution is the same as resolution, except that new variables can be defined. Define new variables $w$ which is equivalent to $l_1 \land l_2$:
$$
(\lnot w \lor l_1) \land (\lnot w \lor l_2) \land (w \lor \lnot l_1 \lor \lnot l_2)
$$
or that
$$
w \Longleftrightarrow ( l_1 \land l_2)
$$
where $l_1, l_2$ are literals, variables that can optionally be negated. Note that $\lnot w \Longleftrightarrow (\lnot l_1 \lor \lnot l_2) \Longleftrightarrow \lnot l_1 \implies l_2$, so that Extended Resolution variables are equivalent to implications. As such it is easy to think of strings as 'implications' which offer a continuous equivalent of Extended Resolution variables. Connected groups of strings must be acting in concert to perform an efficient SAT algorithm which makes $\mathrm{P} = \mathrm{NP}$.
