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.

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.

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.

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.

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.