Cuando tu dispositivo Android está rooteado, deberías poder flashear imágenes. Existe un paquete "gapps" que contiene las aplicaciones de Google (como Gmail, ...) que se entrega con la mayoría de las ROMs AOSP, por lo que puedes flashear eso a través de la recuperación.
Si no me equivoco, esto habilita la Google Play Store en la ROM dada. Creo que el paquete gapps debe ser (en cierta medida) compatible con la ROM en la que se está flasheando.
También existen archivos apk separados que puedes instalar directamente (sin flashear), aunque no tengo experiencia con esos. Y nuevamente, probablemente deben ser compatibles con la ROM que estás utilizando actualmente.
Por favor, consulta xda-developers.com para obtener más información.