From Recife (reached through Guararapes International Airport), either (i) sign up for an organized tour group to Nova Jerusalém, (ii) rent a car and drive to Brejo da Madre de Deus, or (iii) take a intercity bus to Brejo da Madre de Deus.
From Recife, the main route to Nova Jerusalém goes along the modern BR-232 interstate highway, through the cities of Gravatá and Caruaru. In Caruaru, take BR-104 in the direction of Campina Grande. At the Trevo do Cangaceiro de Pedra crossways, take state highway PE-145, which leads to Nova Jerusalém (22 kilometers).
Alternative routes: (i) BR-408, PE-90 and BR-104 (through Carpina, Surubim and Toritama); (ii) BR-408, PE-95 and BR-104 (through Carpina, Limoeiro, Passira, Riacho das Almas and Caruaru).
Apart from the international airport in Recife, a small local airport can be found in Caruaru.
Recife travel agencies offering packages to Nova Jerusalém:
-- Brejo da Madre de Deus Virtual Tour (by Folha de Sao Paulo) 
Traditional handicrafts. Sculptures in granite. Objects made with straw. Very fine "Renascença" lace ana embroidery.
The municipal seat of Brejo da Madre de Deus is located 20 km away. Historic and archeological museum, colonial buildings, typical Northeastern street market, Serra da Prata Lookout (1,000 meters above sea level).