First, having seen the edited version of Martin's question, let's quickly dispose of the construction of the free symmetric monoidal category generated by a category $C$. Objects are tuples $(x_1, \ldots, x_n)$ of objects of $C$. Morphisms are labeled permutations, where permutations are conveniently visualized as string diagrams, each string being labeled by a morphism in $C$. To compose such labeled diagrams, just compose the string diagrams, composing the labels of strings in $C$ along the way.

The free symmetric monoidal category $Sym(M)$ on a monoidal category $M$ is formed from the free symmetric monoidal category $S (U M)$ on the underlying category $U M$ by adjoining isomorphisms $\phi_{x_1, \ldots, x_n}: (x_1, \ldots, x_n) \to x_1 \otimes \ldots \otimes x_n$, where the $x_i$ are objects of $M$, the expression $(x_1, \ldots, x_n)$ is the formal monoidal product in $S(UM)$, and $x_1 \otimes \ldots \otimes x_n$ is the tensor product in $M$.

More precisely, define the objects of $Sym(M)$ to be tuples $(x_1, \ldots, x_n)$ of objects of $M$. Define morphisms $(x_1, \ldots, x_n) \to (y_1, \ldots, y_m)$ to be equivalence classes of pairs $(p, f)$ where $p$ is a permutation on $n$ elements, and $f$ is an $M$-labeled *planar forest* of $m$ rooted trees. (You should think here of the free multicategory generated by a category.) Formally, a planar forest can be described as a functor $[n]^{op} \to \Delta$ where $n$ is the category $1 \leq \ldots \leq n$ and $\Delta$ is the category of finite (possibly empty) ordinals. Under the obvious way of drawing such forests, the ordered list of leaves of the forest is labeled by $(x_{p(1)}, \ldots, x_{p(n)})$, and the ordered list of roots by $(y_1, \ldots, y_m)$. Edges are labeled by objects of $M$, and each internal node with $k$ inputs labeled (in order) by $m_1, \ldots, m_k$ and output $m$ is labeled by a morphism $f: m_1 \otimes \ldots \otimes m_k \to m$.

There is an evident way, using the monoidal structure of $M$, of evaluating such a labeled forest $f$ as a morphism $ev(f): x_{p(1)} \otimes \ldots \otimes x_{p(n)} \to y_1 \otimes \ldots \otimes y_m$ in $M$. We consider two arrows $(p, f)$ and $(p', f')$ to be equivalent if $p = p'$ as permutations and $ev(f) = ev(f')$.

Now we define composition of pairs. The main idea is to rewrite the composition of a forest followed by a permutation,

$$(x_1, \ldots, x_n) \stackrel{(1, f)}{\to} (y_1, \ldots, y_m) \stackrel{(q, 1)}{\to} (y_{q(1)}, \ldots, y_{q(m)}),$$

into a form $(p, f')$ forced by the naturality requirement of the symmetry isomorphism. Namely, if $\bar{x}_i$ is the tuple of leaves of the tree whose root is $y_i$, then we have a block permutation $bl(q)$ taking $(\bar{x}_1, \ldots, \bar{x}_m)$ to $(\bar{x}_{q(1)}, \ldots, \bar{x}_{q(m)})$. The permutation $q$ can also be applied to the $m$ trees of the forest by reordering the trees, yielding a new forest $\mathrm{perm}_q(f)$, and the composition $(q, 1) \circ (1, f)$ is defined to be $(bl(q), \mathrm{perm}_q(f))$. Then, if we have $(p, f): (x_1, \ldots, x_n) \to (y_1, \ldots, y_m)$ and $(q, g): (y_1, \ldots, y_m) \to (z_1, \ldots, z_p)$, we define their composite to be

$$(bl(q) \circ p, g \circ \mathrm{perm}_q(f))$$

where the first component is by composing permutations and the second is by the usual way of composing forests by plugging in roots of one planar forest of trees into leaves of another.

Remaining details that all this works will be left to the reader. I will remark that the key rewriting procedure above is an instance of a kind of distributive law; there are some more details to this effect in some notes on my nLab web; see here.

anysense! – Todd Trimble♦ Dec 29 '12 at 23:27