Hola alano, los permisos de navegación para ríos y embalses los expiden las Confederaciones Hidrográficas. En Extremadura, si piensas moverte bastante, es posible que necesites uno de la del Tajo y otro de la del Guadiana, no?. Mira en sus correspondientes páginas webs, ambas tienen colgados unos formularios de solicitud que te puedes bajar (también hay tlfs a los que puedes llamar), rellenar y enviar por FAX (o presentar en persona). Te contestarán diciendo cuanto has de pagar, pero no te pongas nervioso: suelen tomarse su tiempo (al menos los del Tajo).
Ah, no sé si los del Tajo habrán solucionado ya esto, pero hace no mucho, en la web y el formulario parecía que has de pedir permisos para embalses/ríos concretos y que a más sitios más pagas. Hasta 2007 era así, pero ahora ya no, pagas lo mismo pidas el número que pidas, así que, si no hubieran corregido este absurdo, asegúrate de poner todos los embalses y ríos donde esté permitida la navegación (la lista también está en la web). Para el Guadiana, al menos cuando yo miré, el permiso ya era para toda la cuenca. Siempre que esté permitida la navegación, claro. Hay espacios protegidos y demás con reglamentación especial.
Espero que esto te oriente un poco.