If $M$ is finite-dimensional and second-countable, $\Gamma(E,M)$ is always finitely generated over $C^\infty(M)$. To see this, first note that $M$ has a finite covering $\{U_1,\dots,U_{k}\}$ consisting of open sets over which $E$ is trivial. (See this post for an explanation. Using the theory of topological covering dimension, you can show that it's possible to cover $M$ with $n+1$ such sets, where $n$ is the dimension of $M$.) For each $i=1,\dots,k$, let $(\sigma_{i1},\dots,\sigma_{im})$ be a smooth local frame for $E$ over $U_i$ (where $m$ is the rank of $E$). Let $\{\phi_1,\dots,\phi_{k}\}$ be a smooth partition of unity subordinate to $\{U_1,\dots,U_k\}$, and for each $i,j$, define
$$
\tilde\sigma_{ij} = \left\{
\begin{matrix}
\phi_i\sigma_{ij}, & \text{on }U_i,\\
0 & \text{on }M\smallsetminus \text{supp }\phi_i.
\end{matrix}
\right.
$$
For each $i$, let $V_i\subseteq M$ be the open set on which $\phi_i>0$. Because the $\phi_i$'s sum to $1$,
$\{V_1,\dots,V_k\}$ is also an open cover of $M$. The
$\tilde \sigma_{ij}$'s are smooth global sections of $E$, with the property that their restrictions to $V_i$ span $\Gamma(E,V_i)$ for each $i$.
Let $\{\psi_1,\dots,\psi_k\}$ be a smooth partition of unity subordinate to $\{V_1,\dots,V_k\}$.
Now suppose $S$ is a global smooth section of $E$. Over each $V_i$, we can choose smooth functions $f_{i1},\dots,f_{im}\in C^\infty(V_i)$ such that $S|_{V_i} = f_{i1}\tilde \sigma_{i1}+\dots+f_{im}\tilde \sigma_{im}$. Therefore, globally we can write
$$
S = \sum_{i=1}^k \psi_i(f_{i1}\tilde \sigma_{i1}+\dots+f_{im}\tilde \sigma_{im})
= \sum_{i,j} \tilde {f_{ij}} \tilde \sigma_{ij},
$$
where $\tilde {f_{ij}}$ is the globally defined smooth function
$$
\tilde {f _{ij}} = \left\{
\begin{matrix}
\psi_i f _{ij}, & \text{on }V_i,\\
0 & \text{on }M\smallsetminus \text{supp }\psi_i.
\end{matrix}
\right.
$$
Thus the sections $\tilde \sigma_{ij}$ generate $\Gamma(E,M)$.
Best Answer
First of all, it's not true that $\Gamma(E)$ is not free. What is true is that $\Gamma(E)$ might not be free, depending what $E$ is. Specifically, $\Gamma(E)$ is free iff the vector bundle $E$ is trivial.
This more specific statement gives us much more of a clue of how to prove it: we can expect that a basis for $\Gamma(E)$ corresponds to a trivialization of $E$. Indeed, if $E\cong M\times\mathbb{R}^n$ is trivial of rank $n$, then $\Gamma(E)\cong C^\infty(M)^n$: a section of $E$ can be identified with a smooth map $M\to\mathbb{R}^n$, or $n$ smooth maps $M\to\mathbb{R}$.
Conversely, suppose $B$ is a basis of $\Gamma(E)$ over $C^\infty(M)$, and let $m$ be the rank of $E$. Note that if we evaluate the elements of $B$ at any point $p$, they must span $E_p$ (otherwise $B$ could not generate all of $C^\infty(M)$), so $|B|\geq m$. I claim that $|B|=m$. To prove this, fix any point $p\in M$. We can find $s_1,\dots s_m\in B$ such that $s_1(p),\dots,s_m(p)$ is a basis for $E_p$. Then $s_1,\dots,s_m$ are linearly independent at every point in some neighborhood $U$ of $p$, and so give a local trivialization of $E$ on $U$. In particular, if $s\in B\setminus\{s_1,\dots s_m\}$ we can write $s=\sum_{i=1}^m c_is_i$ on $U$, for some smooth functions $c_i$ on $U$. Letting $\varphi\in C^\infty(M)$ be a bump function supported on $U$, we then have $$\varphi s=\sum_{i=1}^mc_i\varphi s_i$$ on all of $M$, where $c_i\varphi\in C^\infty(M)$. This is a nontrivial relation between elements of $B$, contradicting the assumption that they were a basis.
Thus no such $s$ can exist, and $B=\{s_1,\dots,s_m\}$ has $m$ elements. It now follows that $s_1(q),\dots,s_m(q)$ are a basis for $E_q$ for all $q\in M$, so $s_1,\dots,s_m$ give a trivialization of $E$.