В новом API Карт Google для Android мы можемдобавить маркер, но нет способа (легко) удалить один.

Мое решение - держать маркеры на карте и перерисовывать карту, когда я хочу удалить маркер, но это не очень эффективно.

private final Map<String, MarkerOptions> mMarkers = new ConcurrentHashMap<String, MarkerOptions>();

private void add(String name, LatLng ll) {
  final MarkerOptions marker = new MarkerOptions().position(ll).title(name);
  mMarkers.put(name, marker);

  runOnUiThread(new Runnable() {
    @Override
    public void run() {
      mMap.addMarker(marker);
    }
  });
}

private void remove(String name) {
  mMarkers.remove(name);

  runOnUiThread(new Runnable() {
    @Override
    public void run() {
      mMap.clear();

      for (MarkerOptions item : mMarkers.values()) {
        mMap.addMarker(item);
      }
    }
  });
}

У кого-нибудь есть идея получше?