While there are more mathematical definitions available, an appropriate working definition of locally asymptotically $\textrm{AdS}_3$ is that the line-element in Gaussian normal coordinates for $\rho\to\infty$ must take the form
\begin{equation}
ds^2 = d\rho^2 + (\gamma_{ij}^{(0)} e^{2\rho} + {\rm subleading}_{ij}) dx^i dx^j
\end{equation}
where $\gamma_{ij}^{(0)}$ is the 2-dimensional Minkowski metric and "subleading" means "not diverging as fast as $e^{2\rho}$".
You can easily convince yourself that the BTZ black hole (and any other asymptotic AdS$_3$ space-time you might have encountered) can be written in this form.
In 3-dimensional vacuum Einstein gravity the asymptotic solutions to the equations of motion imply that the subleading terms must fall off as in the Brown-Henneaux boundary conditions (BH bc's) provided in Olof's answer.
However, it is not true that BH bc's are necessary for asymptotically $\textrm{AdS}_3$ behavior. You can obtain as asymptotic symmetry algebra (ASA) two copies of the Virasoro algebra even for weaker boundary conditions. The question of whether or not such boundary conditions are useful depends on the theory under consideration.
Permit me to given an example that I know quite well: In topologically massive gravity at a certain critical point one should allow logarithmic violations of the BH bc's in order to accommodate the full normalizable spectrum of linearized fluctuations around $\textrm{AdS}_3$ and to avoid the elimination of otherwise valid classical solutions. See http://arxiv.org/abs/arXiv:0808.2575, in particular Eq. (8), which displays violations of the BH bc's in two entries of the metric. Nevertheless, one can show that one has two copies of the Virasoro algebra as ASA, and that the asymptotic charges are finite and conserved.
Quite generally, a reasonable strategy to find the "right" boundary conditions is to weaken them as much as possible, but without creating inconsistencies, like infinite or non-conserved charges. This can be sometimes a bit of an art and may require physical input.