Exponential Distribution Function If $X\sim \text{Exp}(X)$  then for all positive $a$ and $b$, $P(X>a+b\mid X>a)=P(X>b).$ So given independent random variables $X \sim \text{Exp}(\lambda)$, $Y \sim\text{Exp}(\mu)$ we would like to know $P(Y>a+X\mid Y>a)$ with the intention of using this for probabilities that a gap between two order statistics is of a certain magnitude.

So $P(Y>a+X\mid Y>a)=P(Y>X)$. Why is $P(Y>X) = \mathbb{E}[\exp(\mu X)]= \frac{\lambda}{\lambda+\mu}$? Is it because the above theorem is for fixed $a$, and $X$ "varies", meaning that we need to integrate and get an expectation value in the process? 

I also think this will help show, given $Z\sim \text{Exp}(\nu)$, also independent, $P(Y>X\cap Z>X)=\frac{\lambda}{\lambda+\mu+\nu}$. This is referring to the more general
$P(\bigcap_{k=1}^n\{X_k>a+b_k\} \mid \min(\{X_k\})>a)=P(\bigcap_{k=1}^n\{X_k>b_k\})$ which imples, by setting $b_k=X$ $\forall k$, that 
$$P(\min(Y,Z)>a+X\mid \min(Y,Z)>a)=P(\{Y>a+X\}\cap\{Z>a+X\}\mid\min(Z,Y)>a)=P(\{Z>X\}\cap \{Y>X\})$$
Which provided the above expectation identity holds will give me the final expression
$$P(\min(Y,Z)>a+X\mid a<\min(Y,Z))=\frac{\lambda}{\lambda +\mu+\nu}$$
 A: I now see that you wanted $\Pr(Y>X)$ rather than $\Pr(X>Y)$.  Below is what I posted originally, saying that one needs to construe "$X\sim\mathrm{Exp}(\lambda)$" as meaning $X$ has an exponential distribution with expected value $\lambda$, rather than that is means $X$ has an exponential distribution with rate $\lambda$.  But in order to get $\Pr(Y>X)=\lambda/(\lambda+\mu)$ rather than $\Pr(X>Y)=\lambda/(\lambda+\mu)$, one actually needs to do it the other way around.  So make the trivial changes in the argument originally posted here, replacing every $\lambda$ with $1/\lambda$ and similarly for $\mu$.  For the sake of completeness, I'll give the argument here:
If $X\sim\mathrm{Exp}(\lambda)$ then $\Pr(X>x) = e^{-\lambda x}$, So $\Pr(X>Y\mid Y)=e^{-\lambda Y}$.  The law of total probability tells us that $\Pr(Y>X)=\mathbb E(\Pr(Y>X\mid X))$.  So
$$
\mathbb E(\Pr(Y>X\mid X)) = \mathbb E(e^{-\mu X}) = \int_0^\infty e^{-\mu x} \Big(e^{-\lambda x}\,(\lambda\,dx)\Big) = \int_0^\infty e^{-(\lambda+\mu)x} \, \mu\,dx = \frac{\lambda}{\mu+\lambda}.
$$
Original answer:
This will answer part of what you're asking.  If $X\sim\mathrm{Exp}(\lambda)$ then $\Pr(X>x) = e^{-x/\lambda}$, So $\Pr(X>Y\mid Y)=e^{-Y/\lambda}$.  The law of total probability tells us that $\Pr(X>Y)=\mathbb E(\Pr(X>Y\mid Y))$.  So
$$
\mathbb E(\Pr(X>Y\mid Y)) = \mathbb E(e^{-Y/\lambda}) = \int_0^\infty e^{-y/\lambda}\Big(e^{-y/\mu}\,(dy/\mu)\Big) = \int_0^\infty e^{-y\left(\frac1\lambda+\frac1\mu\right)} \, \frac{dy}{\mu}
$$
$$
=\frac1\mu\cdot\frac{1}{\frac1\lambda+\frac1\mu} = \frac{\lambda}{\mu+\lambda}.
$$
(For this to be right, one must assume that "$X\sim\mathrm{Exp}(\lambda)$" means $X$ has an exponential distribution with expected value $\lambda$, rather than that is means $X$ has an exponential distribution with rate $\lambda$.)
