No recuerdo toda la normativa, pero creo que está permitido el vivaqueo al raso o con un máximo de tres tiendas que solo podrán estar montadas desde el atardecer hasta el amanecer.
En otros parques naturales no lo sé, en la Sierra de las Nieves hay que comunicarlo a las oficinas del parque natural y recoger la autorización, nunca nos han puesto pegas.

Saludos.

Buenas.

Como te comenta el compañero Ubio, como norma general, en Andalucía, está permitido el vivaqueo al raso y la acampada nocturna (tienda de campaña montada una hora antes de anochecer y desmontada al amanecer), sin necesidad de pedir permiso o autorización.

Sin embargo hay particularidades, y es que si el número de personas que realizan la actividad es superior a 15 o el número de tiendas excede de 3, siempre habrá que pedir autorización.

Además, cada espacio natural protegido puede tener sus particularidades, prohibiendo esta actividad en determinadas zonas de reserva o de especial fragilidad medioambiental, así que si vuestra ruta atraviesa algún Parque Natural, es recomendable llamar al mismo y que ellos os asesoren.

Si preguntas por rutas, en Málaga hay varias zonas de travesías interesantes: Sierra de Las Nieves, Valle del Genal, Sierra Bermeja, Macizo de Líbar, Sierras Tejeda y Almijara, etc

Te pongo algunos enlaces:
GR242 - http://www.fedamon.com/index.php/home-6/2013-04-16-17-25-48/11-federacion/173-sendero-gr-242
GR243 - http://www.fedamon.com/senderos/grs/gr243.htm
GR249 - http://www.gransendademalaga.es/

Hace poco realicé el GR243 integro, y la primera parte, desde Ronda hasta Tolox es muy recomendable para realizar en un par de jornadas o tres.
http://www.cazatormentas.net/foro/reportajes-de-senderismo-montaismo-trekking-y-mtb/dias-1-y-2-gr243-sierra-de-las-nieves-(malaga)-ronda-el-burgo-los-sauces/
http://www.cazatormentas.net/foro/reportajes-de-senderismo-montaismo-trekking-y-mtb/gr243-sierra-de-las-nieves-(malaga)-dia-3-los-sauces-yunquera-tolox/

Un saludo.