Adwords tiene un tipo de campaña especial para apps llamada "Campaña universal de aplicaciones". Es bastante eficaz y permite presupuestos bajos.
En estas campañas no se diseñan anuncios, los generan automáticamente desde la ficha de Google Play y aparecen en el propio Google Play y en el buscador.
Sólo tienes que indicar 4 frases publicitarias para que salgan en el anuncio. Esas 4 frases son muy importantes por lo que tendrás que buscar términos que tengan muchas búsquedas y a ser posible que coincidan con el título y textos que describen tu app.
Durante una semana veras que la campaña está en "fase de aprendizaje", ya que AdWords ajusta pujas por sí mismo con respecto al presupuesto que le has indicado y el CPC. Luego ya quedará normalizada y podrás ver día a día el % de conversiones.
Ver el archivo adjunto 99124
Ojo, no digo que esto sea mejor ni peor que otros métodos que aquí te han dicho. Como has preguntado por AdWords sólo quería decirte cómo hacerlo.