Bueno tienes varias opciones:
1.- Usar google maps con tarifa de datos
2.- Crearte tu mapas offline a partir de google, esto se hace con trekbuddy atlas creator. Selecciones la zona, los niveles de zoom y el formato de salida (android oruxmaps)
3.- Partir de mapas ya hechos , por ejemplo para el ozi explorer, y convertirlos para orux con la aplicación oruxmaps desktop- Esto es algo mas complicado ya que quizas debas seleccionar el datum- Por lo general será el Europeas ED 50
Todo esto como dice el compañero esta explicado en la pagina web de oruxmaps, por otra parte creo recordar que existen hilos abiertos en la parte de software para android .Es cuestión de que busques pero creo que puedes descargar infinidad de mapas,