Existem algumas abordagens diferentes a serem consideradas:

1) Use um produto de banco de dados que implemente multi-master ou MVCC (Multiversion Concurrency Control) e roda no Android + seu servidor. Existem alguns exemplos na página da wikipedia MVCC , sendo o CouchDB uma solução comum. Existe um TouchDB-Android port que é otimizado para rodar no Android e suporta replicação para CouchDB.

2) Seus requisitos podem ser simples (ou únicos) o suficiente para justificar o lançamento de sua própria solução. Uma solução comum seria usar SQLite no Android e sincronizar informações com um servidor remoto por meio de uma API (provavelmente RESTful).

Não é essencial usar a mesma solução de banco de dados no dispositivo móvel e no servidor, mas usar um esquema e uma linguagem de consulta semelhantes provavelmente o manterá mais são.