$\newcommand{\til}{\tilde}$
This is an attempt to prove rigorously that there exists an open subset $\Omega$ of the normal bundle to $S$, such that $exp:\Omega \to M$ is a bijection. This proof seems to work only when $S$ is compact.
Reminder-we assume the following:
1) For every point in $M$, there exist a unique closest point in $S$
2) For every point in $M$, there exist a unique minimizing geodesic from it to $S$
Define $\Omega=\{(s,v)\in NS|\, \, exp_s(tv) \, \text{ is the unique minimizing geodesic from } s \in S \text{ to } exp_s(v) \}$
Assumption (2) (together with the fact minimizing geodesics are orthogonal to the submanifold) implies that $exp: \Omega \to M$ is a bijection. (This is the only candidate).
Assume by contradiction $\Omega$ is not open, then there exists a point $(s,v)$ in $\Omega$, and a sequence $(s_n,v_n)$ in $NS\setminus\Omega$ converging to $(s,v)$. By the definition of $\Omega$, there exists a sequnce $(\til s_n,\til v_n) \in NS$ s.t $exp_{\til s_n}\til v_n=exp_{s_n}v_n$, $|\til v_n| < |v_n|$ (the norms are taken w.r.t the metric at the different base points). since $S$ is compact, $NS$ is also compact, so we can assume $(\til s_n,\til v_n)$ is converging to some $(\til s,\til v) \in NS$. Then, continuity of $exp$ forces $exp_{\til s}\til v=exp_sv$, and continuity of the metric forces $|\til v| \le |v| $.
The only thing we can conclude is that $(s,v)=(\til s,\til v)$....
Actually I think $\Omega$ must be closed: If $\Omega \ni (s_n,v_n) \to (s,v)$ then $exp_{s_n}v_n \to exp_sv$. It is not hard to see that if there is a geodesic from $S$ to $exp_sv$ whose length is smaller than $|v|$, then the $v_n$ won't be the optimal lengths of geodesics from $S$ to $exp_{s_n}v_n$, for $n$ sufficiently large.
I am trying to fill in some details based on Deane's original answer (now changed) and Willie's comments, for the case when $M$ is an open Riemannian manifold and $S\subset M$ a submanifold such that there is a unique minimal geodesic joining each $x \in M$ to $\tilde{s}(x) \in S$.
Given $v \in T_xM$, Let $\alpha(\tau)$ be a path in $M$, $\alpha(0)=x,\dot \alpha(0) =v$. Given $\alpha$ there exists a unique 1-parameter family of of constant speed minimal geodesics along $\alpha$, i.e:
$f: (t,\tau) \in [0,1] \times (-\delta,\delta) \rightarrow M$ such that:
$$f(0,0) = x, f(1,0) = \tilde{s}(x), \,f(t,0) \text{ is the unique minimizing geodesic from } x \text{ to } \tilde s(x),$$ $$ f(0,\tau)=\alpha(\tau), \, f(t,\tau) \text{ is the unique minimizing geodesic from } \alpha(\tau) \text{ to } \tilde s(\alpha(\tau))$$
Notice, that the associated Jacobi field is $J(t)=\frac{\partial f}{\partial \tau} (t,0)$, and that $\tilde s(\alpha(\tau))=f(1,\tau)$, hence
$$\frac{d}{d\tau}|_{s=0}\tilde s(\alpha(\tau))=\frac{\partial f}{\partial \tau} (1,0)=J(1)$$
The Jacobi field $J(t)$ satisfies $J(0) = \dot \alpha(0)=v$. We would like to show that $J(1)$ is in fact the directional derivative of $\tilde{s}$ in the direction $v$. A-priori, $J$ might depend on the chosen path $\alpha$ which represents $v \in T_xM$. (Note that $J(1)$ depends on $f(1,\tau)=\tilde s(\alpha(\tau))$).
In order to do so we will show $\frac{DJ}{Dt}(0)$ is determined only by $v$. (Since a Jacobi field $J(t)$ is uniquely determined by $J(0),\frac{DJ}{Dt}(0)$ this finishes the proof of independence).
We can represent the family $f$ via the exponential map as follows: $$f(t,\tau)=exp_{\alpha(\tau)}\big(tv(\tau)\big) $$
$$\frac{DJ}{Dt}(t)=\frac{D}{Dt}\frac{\partial f}{\partial \tau} (t,0)=\frac{D}{D\tau}\frac{\partial f}{\partial t} (t,0)$$
Note that,
$$\frac{D}{D\tau}\frac{\partial f}{\partial t} (t,\tau)=\frac{D}{D\tau}d(exp_{\alpha(\tau)})_{tv(\tau)}(v(\tau)),$$
So
$$ \frac{DJ}{Dt}(0)= \frac{D}{D\tau}d(exp_{\alpha(\tau)})_0(v(\tau))|_{\tau=0}=\frac{D}{D\tau}(v(\tau))|_{\tau=0}=\frac{Dv}{D\tau}(0)$$
Here I am stuck. How can we show $\frac{Dv}{D\tau}(0)$ depends only on $v$ (and not on $\alpha$)?
Other points that need clarification:
1) Demonstrate linearity in $v$:
For a function to be differentiable, the directional derivatives needs to be linear in their arguments. Of course, since Jacobi equation is linear, and we know $J_v(0)=v$ (which is linear), then if we could show $\frac{DJ_v}{Dt}(0)$ depends linarly on $v$ we were done.
2) Finally, linear behaviour of the directional derivatives does not in general imply differentiability.
