Edit: See the end for a summary of this answer
I disagree with the statement "One can construct an appropriate surface patch locally in a neighborhood of each point". In fact, there are local obstructions to the existence of the desired surface. Let $\gamma:(-\epsilon,\epsilon) \rightarrow \mathbb{R}^3$ be an embedded arc parameterized proportional to arc length and let $S \subset \mathbb{R}^3$ be a smooth surface containing $\gamma$. Then $\gamma$ is a geodesic on $S$ if and only if $\gamma''(t)$ is orthogonal to the tangent plane of $S$ for all $t$. The tangent planes of $S$ thus give a smoothly varying family of planes in the restriction to $\gamma$ of the tangent bundle of $\mathbb{R}^3$ which are orthogonal to $\gamma''$. Such a family of planes need not exist. The problem arises at points where $\gamma''(t)=0$; it is clear what the tangent plane to $S$ must be elsewhere.
For example, let $\gamma_1:(-\epsilon,\epsilon)\rightarrow \mathbb{R}^3$ be a smooth embedded curve with the following properties.
- For all $t$, we have $\|\gamma_1'(t)\| = 1$. In particular, $\gamma_1$ is parameterized proportional to arc length.
- For $-\epsilon<t\leq 0$, we have $\gamma_1(t) = (0,0,t)$.
- For $0<t<\epsilon$, we have $\gamma_1''(t) \neq 0$ and $\gamma_1(t) \in \{(x,y,z)\text{ $|$ }z > 0\}$.
Such curves are easy to construct. Now, of course, we might have already found a problematic curve, but let's assume that we haven't, so there exists a surface $S_1$ in $\mathbb{R}^3$ containing $\gamma_1$ such that $\gamma_1$ is a geodesic in $S_1$. For $0<t<\epsilon$, let $n_1(t) \in \mathbb{P}(\mathbb{R}^3)$ be the line in the direction $\gamma_1''(t)$. We know that the tangent plane to $S_1$ at $\gamma_1(t)$ is the orthogonal complement of $n_1(t)$. This implies that $v_1:=\lim_{t \mapsto 0^+} n_1(t)$ exists: it is the orthogonal complement to the tangent plane to $S_1$ at $(0,0,0)$. The key point here is that the tangent plane to $S_1$ at $(0,0,0)$ is uniquely determined by $\gamma_1$. It is clear that $v_1 \neq [0,0,1]$.
Let $M:\mathbb{R}^3 \rightarrow \mathbb{R}^3$ be the orthogonal linear map obtained by composing the reflection in the $z$-axis with a small rotation in the $xy$-plane.
Define $\gamma_2:(-\epsilon,\epsilon) \rightarrow \mathbb{R}^3$ via the formula
$$\gamma_2(t) = M(\gamma_1(-t)).$$
The following then hold.
- For all $t$, we have $\|\gamma_2'(t)\| = 1$. In particular, $\gamma_2$ is parameterized proportional to arc length.
- For $0 \leq t < \epsilon$, we have $\gamma_2(t) = (0,0,t)$.
- For $-\epsilon<t<0$, we have $\gamma_2''(t) \neq 0$ and $\gamma_2(t) \in \{(x,y,z)\text{ $|$ }z < 0\}$.
- For $-\epsilon<t<0$, define $n_2(t) \in \mathbb{P}(\mathbb{R}^3)$ to be the line in the direction
$\gamma_2''(t)$. Then $v_2:=\lim_{t \mapsto 0^-}n_2(t)$ exists and is different from $v_1$ (this is the point
of the rotation in the $xy$-plane in the definition of $M$).
Now define $\gamma:(-\epsilon,\epsilon) \rightarrow \mathbb{R}^3$ via the formula
$$\gamma(t) = \begin{cases}
\gamma_2(t) & \text{if $-\epsilon<t\leq 0$},\\
\gamma_1(t) & \text{if $0<t<\epsilon$}. \end{cases}$$
The second condition on $\gamma_1$ and $\gamma_2$ implies that $\gamma$ is a smooth curve. For $-\epsilon<t<\epsilon$
satisfying $t \neq 0$, we have $\gamma''(t) \neq 0$; define $n(t) \in \mathbb{P}(\mathbb{R}^3)$ to be the line
in the direction of $\gamma''(t)$. We then have
$$\lim_{t \mapsto 0^+} n(t) = v_1$$
and
$$\lim_{t \mapsto 0^-} n(t) = v_2.$$
These are different, so $\lim_{t \mapsto 0} n(t)$ does not exist. This implies that $\gamma$ cannot possibly
be a geodesic in any surface.
Of course, $\gamma$ is not a closed curve, but it is easy to close it up to a simple closed unknotted curve.
In this edit, I'll comment on further obstructions. Let's assume that the desired family of planes on $\gamma$ exists. Using a tubular neighborhood, it is easy to find a small "strip" around $\gamma$ on which $\gamma$ is a geodesic. As David points out, this strip might be a Mobius band, which is bad, so let's assume that it is an annulus $A$ with boundary components $\alpha_1$ and $\alpha_2$. There is now a new obstruction: the linking number of $\alpha_1$ with $\gamma$ might be nonzero (nb: it is an easy exercise to see that the linking numbers of $\alpha_1$ and $\alpha_2$ with $\gamma$ must be the same, though since these loops are unoriented these linking numbers are only well-defined up to signs). This is a problem because we want $\alpha_1$ to bound a disc in $\mathbb{R}^3 \setminus \gamma$, which since $\gamma$ is an unknot is homeomorphic to the result of removing a point from an open disc cross $S^1$; in particular, $\pi_1(\mathbb{R}^3 \setminus \gamma) = \mathbb{Z}$. The linking number of $\alpha_1$ with $\gamma$ is the image of $\alpha_1$ in $\pi_1(\mathbb{R}^3 \setminus \gamma)$. So we have to assume that this linking number is $0$. Letting $U$ be a closed tubular neighborhood of $\gamma$ containing $A$ with $\partial A \subset \partial U$, we have $\pi_1(\mathbb{R}^3 \setminus \gamma) = \pi_1(\mathbb{R}^3 \setminus U)$. We deduce that $\alpha_1$ is nullhomotopic in $\mathbb{R}^3 \setminus U$. Applying Dehn's Lemma (which is overkill in this situation, but why not?), we see that $\alpha_1$ bounds a disc $D_1$ in $\mathbb{R}^3 \setminus U$. We now want $\alpha_2$ to bound a disc in $\mathbb{R}^3 \setminus (A \cup D_1)$, but this is easy since $A \cup D_1$ is homeomorphic to a closed disc, so $\mathbb{R}^3 \setminus (A \cup D_1)$ is homotopy equivalent to $\mathbb{R}^3 \setminus \{x_0\}$ for a point $x_0 \in A \cup D_1$; in particular, $\pi_1(\mathbb{R}^3 \setminus (A \cup D_1)) = 0$.
I want to close with one further remark about the above. Assuming it exists, the family of planes that was the input to the above construction is unique exactly when the set of points on $\gamma$ where $\gamma'' \neq 0$ is dense. But if there exists an interval on which $\gamma''=0$, then we can use that interval to introduce as many half twists as we need to the planes to get rid of the Mobius band and linking number obstructions.
SUMMARY OF ANSWER Let me summarize the answer, which gives a
set of necessary and sufficient conditions for the existence of the
sphere (whose logic is, alas, a little complicated). First, there is a
"local" obstruction that must be satisfied for the desired sphere to exist. It
can be defined as follows. Let $U \subset \gamma$ be the set of all
points where $\gamma''$ is nonzero. Define
$\phi:U \rightarrow \mathbb{P}(\mathbb{R}^3)$ to take $u \in U$ to the
line in the direction of $\gamma''(t)$. Then for a sphere to exist,
the function $\phi$ must be able to be extended to a function
$\widehat{\phi}:\gamma \rightarrow \mathbb{P}(\mathbb{R}^3)$ such
that $\widehat{\phi}(x)$ is orthogonal to $\gamma'(x)$ for all $x$. This
is a vacuous condition if $\gamma''$ never vanishes.
Now assume that such a $\widehat{\phi}$ exists. If $U$ is not dense
in $\gamma$, then no further conditions are needed: the sphere exists.
Otherwise, two further conditions are needed. Observe that in
this case, by the way, the extension $\widehat{\phi}$ is unique. The
first is that there exits a continuous function
$\widehat{\psi}:\gamma \rightarrow S^2$ such that
$\widehat{\phi}(x)$ is the line in the direction $\widehat{\psi}(x)$
for all $x \in \gamma$. This condition is vacuously satisfied if
$\gamma''$ never vanishes (just take $\widehat{\psi}(x)$ to be the
unit vector in the direction of $\gamma''(x)$). The purpose of
this condition is to ensure that the "strip" defined in the answer is
not a Mobius band. If this condition holds,
then we can define the "winding number" of $\widehat{\psi}$ around
$\gamma$ since $\widehat{\psi}(x)$ lies in the orthogonal complement
of $\gamma'(x)$, which is a great circle in $S^2$. The second
needed condition is that this winding number vanishes.
