Assume we have a probability measure $\mu$ on $\mathbb R^n$. Assume it satisfies $$ \mu(x > u) \le Ce^{au} \ \ \forall u > 0 $$ In other words, its tail is dominated by an exponential function. Then, how to prove Poincare inequality? $$ Var_{\mu}f \le K\int\nabla f^2d\mu $$

$\begingroup$ You can't, without additional assumptions. Suppose $\mu$ has discrete support, say for example it's a Poisson distribution on $\mathbb{R}$, and $f$ is constant on a neighborhood of each point in the support of $\mu$. $\endgroup$ – Mark Meckes Mar 8 '13 at 1:42
As Mark Meckes already pointed out, this is not enough to proof a Poncaré inequality.
If you are interested in the case where $\mu$ is absolutely continuous, then there are conditions formulated in terms of the logdensity of $\mu$, i.e. $\mu$ is of the form $$ \mu(\mathrm{d}x) = \exp(H(x)) $$ The minus sign is just convention.
There is a complete characterisation of the constant $K$ for the real line via the Muckenhoupt functional. Therefore let $m$ be the median of $\mu$, i.e. $\mu((\infty,m))=\mu((m,\infty))=1/2$, then define $$ \begin{align} B_+ &= \sup_{x\geq m} \left( \int_{m}^x \exp(H(y))\;\mathrm{d}y\ \int_{x}^\infty \exp(H(y)) \; \mathrm{d} y \right) \\\\ B_ &= \sup_{x\leq m} \left( \int_{x}^m \exp(H(y))\;\mathrm{d}y \ \int_{\infty}^x \exp(H(y)) \; \mathrm{d}{y} \right) \end{align}$$ Then, one has $$ \frac{1}{2} \max\{B_,B_+\} \leq K \leq 4 \max\{ B_, B_+\} $$ I.e. the Poncaré constant can be recovered upto a factor of $8$.
On $\mathbb{R}^n$ there is the theory of Lyapunov functions, which give sufficient conditions for Poincaré inequalities. See A simple proof of the Poincaré inequality by Bakry et. al. There, two prominent assumptions on $H$ which both individually imply a Poincaré inequality are
For some $\alpha>0$ and all $x\geq R>0$ holds $$ \langle x, \nabla H\rangle \geq \alpha x $$
For some $\alpha>0 , c>0$ and all $x\geq R>0$ holds $$ \alpha \nabla H(x)^2  \Delta H(x) \geq 0 $$
Then $\mu$ satisfies a Poincaré inequality with an upper bound on the constant $K$.