There are two things to keep in mind. First, we always need to fix an ample line bundle to speak about stability. Secondly, Intersection Theory is made a way that you can work (at least if $X$ is smooth) on the Grothendieck group $K_0(X)$, so one might consider locally free resolution.
Fix an ample line bundle $H$. To define the degree of any coherent sheaf $F$, you can consider a locally free resolution
$$0\to F_m \to \cdots \to F_1 \to F_0 \to F$$
and define $\det(F)=\prod \det(F_i)^{(-1)^i}$. Then you define
$$\deg(F) = c_1(\det(F))\cdot H^{\dim(X)-1}$$
This definition agrees with the one you state in the case of maximal dimension (see http://www.math.harvard.edu/~yifei/tensor_char_zero.pdf Lemma $1.20$).
Example: If you consider an effective divisor $D\in Pic(X)$, you have the exact sequence $0 \to \mathcal{O}_X(-D) \to \mathcal{O}_X \to \mathcal{O}_D \to 0$, thus $c_1(\mathcal{O}_D)=D$ (as a cycle) and thus $\deg_H(\mathcal{O}_D)=D\cdot H^{\dim X -1} =\deg_H(D)$ (counting multiplicities and taking the sum on irreducible components).
_**Example in a blow-up:*__ Now consider the simple example of $\widetilde{X}=Bl_{p}\mathbb{P}^2 \to \mathbb{P}^2$, the blowup of $\mathbb{P}^2$ at a point $p$. If I take a the strict transform $\widetilde{C}$ of an effective divisor $C\in Pic(\mathbb{P}^2)$, it is still an effective divisor, and $\widetilde{C}=\pi^*C-rE$ where $r$ is the multiplicity of $C$ at $p$. Then there is a resolution
$$0 \to O_{\widetilde{X}}(-D) \to O_{\widetilde{X}} \to O_D \to 0$$
and we obtain once again $c_1(\mathcal{O}_{\widetilde{C}})=\widetilde{C}$. Thus if you fix your ample divisor $T=m\pi^*H - E$ on $\widetilde{X}$, you get
\begin{eqnarray}
\deg_T(\mathcal{O}_{\widetilde{C}}) &=& \widetilde{C}\cdot T\\
&=& (\pi^*C-rE)\cdot(m\pi^*H-E)\\
&=&m\deg_H(C)-r.
\end{eqnarray}
Example for vector bundle :
Consider $\pi : \widetilde{X} \to X$ the blow-up of a smooth projective scheme along a smooth projective subscheme and write $E$ the exeptional divisor. Fix an ample divisor $H$ on $\widetilde{X}$. For a vector bundle $V$ of rank $r$ on $X$, choose a resolution
$$0 \to V_n \to \cdots \to V_0 \to V \to 0,$$
thus $\deg_H(V)= c_1\left(\prod (\det V_i)^{(-1)^{i}}\right)\cdot H^{\dim X-1} = \sum (-1)^i c_1(\det V_i)\cdot H^{\dim X-1}$.
Now define $\widetilde{V}=\pi^* V \otimes O_{\widetilde{X}}(-lE)$ for some $l\in\mathbb{Z}$. As pullback is exact when apply to locally free sheaves, you have the resolution
$$0 \to \pi^* V_n \to \cdots \to \pi^* V_0 \to \pi^* V \to 0.$$
Fix the ample line bundle $T=m\pi^* H - E$ on $\widetilde{X}$. As $c_1(\widetilde{V})=c_1(\pi^*(V)\otimes \mathcal{O}_{\widetilde{X}}(-lE) = c_1(\pi^*V)-rlE$, we obtain
\begin{eqnarray}
\deg_T (\widetilde{V}) &=& (c_1(\pi^* V)-rlE)\cdot T^{\dim X -1}\\
&=&\sum (-1)^ic_1( \det \pi^* V_i)(m\pi^* H^{\dim X-1})+rlE^2 \\
&=& m\deg_H(V)+rlE^2
\end{eqnarray}
In more general settings, I don't know if things go so well. You need to find a locally free resolution of the strict transform, which might be harder as pullback is not exact in general.
For $n>1$, the natural guess would be that $\pi_*\mathcal{O}_{\widetilde{X}}(-nE)=I_{Y/X}^n$, and it's true in this case. For $n<0$, we have $\pi_*\mathcal{O}_{\widetilde{X}}(-nE)=\mathcal{O}_X$.
To show these claims, we'll work locally on $X$. Assume $X=\operatorname{Spec} A$ is affine and $Y$ is cut out by the ideal $I_Y=(f_1,\cdots,f_r)$. Then we get a surjection $A^r\to (f_1,\cdots,f_r)$ which turns in to a surjection of the graded algebras $\operatorname{Sym}(A^r)\to \bigoplus_{m\geq 0} I_Y^m$ corresponding to the closed immersion $\widetilde{X}\hookrightarrow \Bbb P(A^r)$. Here, the exceptional divisor $E$ corresponds to the line bundle $\mathcal{O}_{\Bbb P(A^r)}(-1)|_{\widetilde{X}}$.
Next, via the restriction map $\mathcal{O}_{\Bbb P(A^r)}(m) \to \mathcal{O}_{\Bbb P(A^r)}(m)|_{\widetilde{X}}$ and the canonical isomorphism $\mathcal{O}_{\widetilde{X}}(1)\cong \mathcal{O}_{\widetilde{X}}(-E)$, we see that if $\mathcal{O}_{\Bbb P(A^r)}(n)$ is globally generated, then $\pi_*\mathcal{O}_{\Bbb P(A^r)}(n)\to \pi_*\mathcal{O}_{\widetilde{X}}(-nE)$ will be surjective and thus an isomorphism of line bundles. By identifying $\pi_*\mathcal{O}_{\Bbb P(A^r)}(n) = \operatorname{Sym}^n(A^r)$ and $\pi_*\mathcal{O}_{\widetilde{X}}(-nE)=I^n$, we see that when the global generation condition is satisfied, then we have an isomorphism $\mathcal{O}_{\widetilde{X}}(-nE)\cong I_Y^n$.
By Serre vanishing, this is always the case for any $X,Y$ assuming that $n>>0$. In our case, the argument from the linked post shows that in fact $\mathcal{O}_{\Bbb P(A^r)}(1)$ is globally generated, so $\mathcal{O}_{\Bbb P(A^r)}(n)$ is globally generated for all $n>0$. So we get our claimed isomorphism $\pi_*\mathcal{O}_\widetilde{X}(-nE)\cong I^n_Y$.
For $n<0$, after tensoring the natural exact sequence $0\to \mathcal{O}_\widetilde{X}(nE) \to \mathcal{O}_X\to\mathcal{K} \to 0$ by $\mathcal{O}_\widetilde{X}(-nE)$ we get the sequence $0\to \mathcal{O}_\widetilde{X}\to \mathcal{O}_\widetilde{X}(-nE)\to \mathcal{K}(-nE)\to 0$ (here $\mathcal{K}$ is the structure sheaf of a thickening of $E$). If we prove that $\pi_*\mathcal{K}(-nE)$ has no global sections, then it's the zero sheaf as $X$ is affine, and this would imply $\mathcal{O}_X=\pi_*\mathcal{O}_\widetilde{X}\to \pi_*\mathcal{O}_\widetilde{X}(-nE)$ is an isomorphism.
As $\mathcal{O}_\widetilde{X}(-nE)\cong \mathcal{O}_\widetilde{X}(n)$, we see that it's a negative line bundle, and after restriction to any projective subvariety of $\Bbb P(A^r)$ it will still be a negative line bundle and therefore have no sections. Taking the fiber $\Bbb P(A^r)_y$ for $y\in Y$, we see that this is a projective variety, so there are no sections of $\mathcal{O}_\widetilde{X}(n)$ in the fiber direction along $E\to Y$. But any global section of $\pi_*\mathcal{K}(-nE)$ would come from such a global section of $\mathcal{O}_\widetilde{X}(n)$ because $\mathcal{O}_\widetilde{X}(n)\to \mathcal{K}(-nE)$ is surjective and would remain this way after restricting to $E$. So there cannot be any global sections and we've shown that $\pi_*\mathcal{O}_\widetilde{X}(-nE)=\mathcal{O}_X$ for $n<0$.
Best Answer
This MO post is a great reference if you're ever trying to figure out or remember when for a morphism $f:X\to Y$ we will have $f_*\mathcal{O}_X=\mathcal{O}_Y$.
Here's the relevant portion of that answer for this post, in order to make this answer self-contained:
This applies to your situation as follows: the blowup map $\pi:\widetilde{X}\to X$ is a projective birational map with connected fibers. Since projective and connected fibers are preserved under base change, we see that the base change of this map $E\to Y$ is again projective with connected fibers, so we may also apply the result there, via the Stein factorization described in the first paragraph (even though this last morphism is not birational - $\dim E=\dim X-1\neq \dim Y$).