Since I cannot (yet) post comments, I'll post this as an answer, even though it is more a comment on Joe Silverman's answer.

Let $H$ be the bound for the multiplicative height (so $H = e^h$ if $h$ is a bound for the logarithmic height) of the point you want to find. Then (as is pointed out in Joe's paper) a naive search on the elliptic curve has a complexity of roughly $H^{3/2}$, whereas his algorithm gives you $H$. On the other hand, searching for the point on a 2-covering can be done in time essentially $H^{1/2}$ (the logarithmic height goes down by a factor of 4), and if I remember correctly, this is what mwrank does. Using $n$-coverings for arbitrary $n$, the complexity drops to $H^{1/((n-1)n)}$, but of course the implied constant grows (there are roughly $n^r$ covering curves to consider when the rank is $r$, and the complexity of the lattice computations also goes up, since one has to use rank-$n$ lattices). In addition, of course, you have to add the time you need to compute the $n$-coverings in the first place, which for $n = p$ a prime usually involves computing class and unit groups of fields of degree about $p^2$. For composite $n$, the complexity tends to be better, though.

The exponent $1/((n-1)n)$ comes from two ingredients: the first is that the logarithmic height of the preimage of your point on the covering curve goes down by a factor of $1/(2n)$. The second is the lattice-based point search method mentioned by Noam Elkies in his comment that gives you a complexity of $B^{2/(n-1)}$ for a search for points up to multiplicative height $B$ on a smooth curve in ${\mathbb P}^{n-1}$. Picking a good value of $n$ should lead to something subexponential; I assume this is what Noam was having in mind (his ANTS IV paper describes a version of the lattice-based point search).

The point I want to make is that descent and searching on coverings usually gives you a faster way of finding points than Joes's method, even without knowledge of the exact canonical height (the height is still useful since it gives you a bound for the search). <a href="http://www.dpmms.cam.ac.uk/~taf1000/papers/sixandtwelve.html">Tom Fisher</a> has demonstrated that this can be very effective already for relatively small values of $n$ like 6 or 12.