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.
Best Answer
The Hilbert polynomial of $E$ is some Euler characteristic of the sheaf with the tensor product of some power of the twisting sheaf $\mathcal{O}(1)$. But HRR just gives you this Euler characteristic in terms of the Chern classes.
See here Lemma 1.20. for a proof, if you get lost in the computations.