[This was an irresponsible answer to write six years ago, even with a tongue-in-beak disclaimer to do your own security analysis and find the flaws in it. Please consult the (latest) literature, not this answer. Since it is an accepted answer, however, I can't delete it, so this is the best I can do to stop unwary passersby from tripping over it.]
Here is a simple-minded Ed25519-based multisignature or collective signature scheme, in which Alice and Bob each having their own private key, kept secret from one another, must work together to create a joint signature that a verifier knowing both of their public keys, or only a joint public key, can verify. This is a simplification of a recent IETF internet-draft, [draft-ford-cfrg-cosi], presently under consideration by the CFRG.
$\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\concat}{\mathop{\Vert}}\newcommand{\U}[1]{\underline{#1}}$Let $p = 2^{255} - 19$, a prime; let $E$ be the elliptic curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$$ over $\F_p$ (edwards25519, the twisted Edwards curve birationally equivalent to Curve25519 used in the Ed25519 signature scheme); let $P$ be the unique $\F_p$-rational point on $E$ whose $x$ coordinate is 4/5 and whose $y$ coordinate is ‘positive’, and let $\ell$ be its order; let $H$ be a uniform random choice of function from byte strings to $\Z/\ell\Z$; let $\U Q$ be some byte string encoding of a point $Q \in E(\F_p)$.
To begin, Alice picks a secret scalar $a \in \Z/\ell\Z$ and a secret 32-byte hash key $h_a$, and shares the encoding of the point $A = [a]P$. Bob does likewise with $b$, $h_b$, and $B$. Their joint public key the encoding of is $A + B$.
An Alice/Bob signature on a message $m$ is the encoding of a point $R \in E(\F_p)$ and a scalar $s \in \Z/\ell\Z$ such that $$[s]P = R + [H(\U R\concat \U{A+B}\concat m)](A + B).$$
How do Alice and Bob create such a beast? First, Alice computes $r_a = H(h_a\concat u_a \concat m)$ where $u_a$ is an independent uniform random 32-byte string, and keeps $r_a$ secret but shares $R_a = [r_a]P$; Bob does similarly with $r_b$ and $R_b$. Then they each compute $R = R_a + R_b$. Next, Alice computes $$s_a = r_a + H(\U R\concat \U{A+B}\concat m)\,a,$$ and Bob computes $s_b$ similarly. Finally, to commit the signature creation, they jointly compute $s = s_a + s_b$ and reveal $R$ and $s$.
This is an Alice/Bob signature, because
\begin{align*}
[s]P &= [s_a + s_b]P \\
&= [r_a + r_b + H(\U R\concat \U{A+B}\concat m)\,(a + b)]P \\
&= [r_a]P + [r_b]P + [H(\U R\concat \U{A+B}\concat m)][a + b]P \\
&= R_a + R_b + [H(\U R\concat \U{A+B}\concat m)]([a]P + [b]P) \\
&= R + [H(\U R\concat \U{A+B}\concat m)](A + B).
\end{align*}
Unlike a naive concatenation of two Ed25519 signatures which takes a net 128 bytes of storage, an Alice/Bob signature takes only 64 bytes of storage, and that remains so no matter how many additional signers you add. Conveniently, the resulting Alice/Bob signature is also an Ed25519 signature under the public key $\U{A+B}$, so you can use existing Ed25519 verifiers to verify it.
(Security analysis is left as an exercise for the reader. Hints: Suppose evil Bob knows Alice's public key $A$ before the two of them collectively
publish the joint key $P$. What nefarious deed can Bob commit in that case? If Alice's random number generator is wedged when she makes a signature so it returns the same $u_a$ each time, how can Bob exploit that to do something nefarious with Alice?)
This scheme has various properties:
- Each party's part of the signature was generated by a different private key not known to the other parties.
- All parties must agree to make the signature before it will be accepted by a verifier. We could easily extend the definition of a signature to include a list of the signers, and have a verifier require some threshold of signers before accepting it, at the cost of a little extra space to store a signature (as in draft-ford-cfrg-cosi).
- If we adapted it thus to a threshold scheme, the subset of possible signers who did sign it would not be anonymous to a verifier.
There are variations on the theme of multisignatures: are the signers anonymous to one another, are there thresholds, if there are thresholds is the subset of possible signers who did sign revealed to a verifier? You'll have to look closely at exactly what Bitcoin's scheme is to see which properties it provides. For further background, you might read Micali, Ohta, and Reyzin's paper introducing Schnorr multisignatures, or Bellare and Neven's elaboration on it.
