GoogleのAPIを利用して、座標から住所を取得します。
GoogleのWebサービスに依存しているので、使えない場合があるので注意しましょう。
Android 2.3(API level 9)からisPresent()で、サービスが生きてるかどうかをチェックできるようです。

import java.io.IOException;
import java.util.List;
import java.util.Locale;

import android.content.Context;
import android.location.Address;
import android.location.Geocoder;

public class ReverseGeocode {

    public String point2address(Context context, double latitude, double longitude) throws IOException {

        String string = new String();

        Geocoder geocoder = new Geocoder(context, Locale.JAPAN);

        List<Address> list_address = geocoder.getFromLocation(latitude, longitude, 2);

        if(!list_address.isEmpty()) {
            string = list_address.get(1).getAddressLine(1);
        } else {
            string = "現在地が特定できませんでした。";
        }

        return string;
    }

}

LocationListenerのonLocationChanged等で実行します。

@Override
public void onLocationChanged(Location location) {

    String string = new String();

    ReverseGeocode rg = new ReverseGeocode();

    try {
        string = rg.point2address(this, 
            location.getLatitude(), location.getLongitude()) + "付近";
    } catch (IOException e) {
        e.printStackTrace();
    }

    Toast.makeText(this, string, Toast.LENGTH_SHORT).show();
}

詳細情報はこちらを参照
http://developer.android.com/reference/android/location/Geocoder.html

Android 4.0.3のタブレット端末で、逆ジオコーディングできない現象が発生しました。
色々調査していると、同じ現象が起こっているようですが、再起動したら解決したとのコメントを数件発見したので、試しに再起動してみたら解決しました。
それでもできない場合は、JSONを使用する方法もあるようです。