Ciao.
Premetto che non ho mai usato l'AutoCompleteEditText, che quindi non conosco, perciò quanto sto per scrivere potresti forse usarlo anche con quella.
Il db, in Android, deve per forza essere SQLite. Puoi farlo creare dalla app stessa, nel codice, oppure usare qualche tool esterno (io utilizzo SQLite Database Browswer, che a dispetto del nome, consente anche la creazione, altri preferiscono SQLite Expert).
Aggiungi alla tua app il modulo DBUtils che trovi qui nel sito, che ti aiuta; ad esempio, dopo che hai creato il db esternamente, lo metti nella Tab Files dell'IDE e poi usi il comando di DBUtils per copiarlo da lì alla cartella di lavoro (passo necessario perché altrimenti il db sarebbe in sola lettura, in questo caso).
Infine, per l'autocomplete, sfrutti l'evento Change della EditText in questione, nella quale richiami una query (megliio se metti tutte le operazioni da eseguire sul DB in un modulo separato, per la pulizia del progetto, non per altro) fatta più o meno in questo modo:
"SELECT NumeroAbitanti FROM TuaTabella WHERE NomeCitta LIKE '" & New & "%'"
in cui New è il nuovo testo inserito dall'utente nela EditText, mentre lo digita.
Dopo che ho scritto tutta questa pappardella... lo provo anch'io
[EDIT]
Ho adattato e allegato il progetto di esempio SearchView di Erel per utilizzarlo con un DB.