Working this out in full generality is likely to be rather messy and unenlightening, but there are a few remarks about the nature of the problem (and special cases) that can be made, so I'll put them here.
First, for any $n$-manifold $M$, let $\mathcal{C}_k(M)$ denote the space of $k$-jets of unparametrized, oriented, immersed curves in $M$. This $\mathcal{C}_k(M)$ is well-known to be a manifold of dimension $n+(n{-}1)k$, with $\mathcal{C}_0(M) = M$ and $\mathcal{C}_1(M)$ being the space of oriented lines in the tangent spaces of $M$, etc. If $\phi:M\to N$ is a smooth embedding, it induces a smooth embedding $\mathcal{C}_k(\phi):\mathcal{C}_k(M)\to \mathcal{C}_k(N)$ in the obvious way.
Now, $\mathcal{C}_k(\mathbb{E}^3)$ is acted on by the $6$-dimensional group $G$ of isometries of $\mathbb{E}^3$, and this action is transitive when $k=0$ or $1$. When $k\ge2$, there is an invariant function, $\kappa:\mathcal{C}_k(\mathbb{E}^3)\to \mathbb{R}$ that simply gives the curvature of the $k$-jet of the curve; it is a smooth submersion away from the locus where $\kappa=0$, and the action of $G$ on the locus $\kappa\not=0$ is free. Let $\mathcal{C}^+_k(\mathbb{E}^3)$ denote the locus where $\kappa>0$.
When $k\ge3$, there are well-defined functions $\kappa_i, \tau_j:\mathcal{C}^+_k(\mathbb{E}^3)\to\mathbb{R}$ for $0\le i\le k{-}2$ and $0\le j\le k{-}3$ which are invariant under $G$ and for a given $k$-jet of a curve with $\kappa\not=0$ evaluate in such a way that $\kappa_i$ is the $i$-th derivative of the curvature $\kappa=\kappa_0$ of the curve with respect to (oriented) arclength and $\tau_j$ is the $j$-th derivative of of the torsion $\tau = \tau_0$ of the curve with respect to (oriented) arclength. The fibers of the submersion
$$
\pi_k = (\kappa_0,\ldots,\kappa_{k-2},\tau_0,\ldots,\tau_{k-3}):
\mathcal{C}^+_k(\mathbb{E}^3)\to\mathbb{R}^{2k-3}
$$
are the orbits of $G$.
Now, if you specify a curve $\iota:C\hookrightarrow\mathbb{E}^3$ that has nonvanishing curvature $\kappa>0$, then it determines a curve $\pi_k\circ\mathcal{C}_k(\iota):C\to\mathbb{R}^{2k-3}$ that is
$$
\pi_k\circ\mathcal{C}_k(\iota) = (\kappa,\kappa',\ldots,\kappa^{(k-2)},\tau,\tau',\ldots,\tau^{(k-3)})
$$
Say that the curve $\iota:C\hookrightarrow\mathbb{E}^3$ is $k$-regular if this map is an embedding. (The generic curve will be $k$-regular for all $k\ge 3$.)
Now, given an embedded surface $h:S\hookrightarrow\mathbb{E}^3$, we get an embedding $\mathcal{C}_k(h):\mathcal{C}_k(S)\to \mathcal{C}_k(\mathbb{E}^3)$ and hence a mapping $\pi_k\circ \mathcal{C}_k(h):\mathcal{C}_k(S)\to\mathbb{R}^{2k-3}$. For the 'generic' embedded local surface, this mapping of this $(k{+}2)$-dimensional manifold into $\mathbb{R}^{2k-3}$ will be an embedding as soon as $k\ge 5$ and its image will have positive codimension $k{-}5$ as soon as $k\ge 6$.
What this means is that, given a general curve and a general surface in $\mathbb{E}^3$, one will be able to write down a condition that the functions $(\kappa,\ldots,\kappa^{(4)},\tau,\ldots,\tau^{(3)})$ on the curve must satisfy in order that there be any curve of $6$-jets of curves in the surface that gives those functions. Actually, even at the $5$-jet level, generically, there will be essentially only a finite number of curves in $\mathcal{C}_5(S)$ that will map to the curvature image of the given curve $C$, and if none of these curves are the $5$-jet lifts of a curve in the surface $S$, then there is no solution to the problem.
Thus, for the generic pair of a curve and a surface in $3$-space, the problem is solvable by algebra and differentiation, but it is liable to be quite messy.
Of course, in special cases, you get information at lower order: If the surface $h(S)\subset\mathbb{E}^3$ is a sphere of radius $R$, for example, then the image $\mathcal{C}_3(h)\bigl(\mathcal{C}_3(S)\bigr)$ is obviously invariant under the $\mathrm{SO}(3)$-subgroup of rotations about the center, so the image under $\pi_3$ of this $5$-dimensional manifold only has dimension $2$ in $\mathbb{R}^3$. In fact, the image of this map in $\kappa\kappa_1\tau$-space is given by the surface
$$
\kappa^{-2} + {\kappa_1}^2\tau^{-2}\kappa^{-4} = R^2,
$$
as was established classically. This is why it is easy to characterize spherical curves.
In the more general case that the surface has no continuous ambient symmetries, though, you do not get any relations (other than some possible inequalities) on the curvatures of the curve before you go to the $6$-jet. That is why the general problem is going to be both difficult and have a messy answer, which probably will not be interesting.