First off, visit the Battle Fronier, I'm pretty sure that you battle Flint and Volkner at the gate. After that go through the gate of the Battle Frontier. Leave and surf through a body of water to the east of the Fight Area. You will eventually reach land, trainers, and grass. After you get to the Resort Area, go north through a route with sandstorm weather. At the end, go through a gate at the west and go north to stark mountain. Go with buck through Stark mountain and he gets something from the cavern that Heatran will be in. Talk to him in the Survival Area. Go back to Stark mountain in that cavern and hopefully Heatran is there. I caught one. Hope it's the same for you.
Source: Personal Experience