From Pokémon HeartGold & SoulSilver Wiki

Safari Zone

The first thing you will find is that there are stores near the entrance of the Safari Zone. When you go inside, an old man with a hat will talk with you and propose a challenge. You need to get a Geodude from the Safari Zone and show it to him. (it really needs to be one caught from the Safari Zone since no other will be accepted) So go to the Safari Zone, talk with the guy at the entrance right ahead from the door. Pay 500 (at least here the prices stayed the same for 10 years even after big construction on changing the safari from fucchia to here) and go in. You will see that the 6 areas sometimes change places during the days you don´t show the geodude to the old man... but they are always the same. So catch a Geodude and when you get out of the Safari Zone, go to the pokecenter outside and grab the Geodude you caught. Place him first on your party and go in and talk with the old man. Now it´s the random waiting. He will tell you that there are constructions been made and that he will call you when they are finished. But there is no timetable to finish them (here is like the real world). So go away from the Safari Zone until he calls you. And you will see that his call is impossible to miss since when it arrives you can only answer the phone. So he calls you and you return to the Safari Zone. He will show you a kind of slot machine that is on the right side of the entrance. On that machine you can change the regions inside the Safari Zone. The old man will challenge you to a new game: Catch a Sandshrew. So you need the desert region into the ones that are open. So go to the machine and change all the 6 regions. There are 12 different regions to use. So change them all if you already caught every pokemon that you found inside the first 6. The Sandshrew is available widly on the desert (bright yellow almost white region). So catch one and keep exploring the regions for new pokemons. When you complete your Safari Game go to the pokecenter and grab the Sandshrew. Go talk with the old man again inside the Safari Gate. He will advance to the machine and tell you that there are a few things being made to be used in the Safari Zone. So, again, you have to wait for his call. And you will see that he changes to the other side of the table. So now you have to wait at least 1 day (it can be more days...)for the call.

After finding Sandshrew and receiving a call from the gate guy

Next thing that will open is the first 6 items. Those items can be placed on any area just by facing a position and pressing A. A new menu will appear and let you choose what item you want to place down.