>In Pokémon HeartGold and SoulSilver, Mystery Gift is automatically unlocked after receiving the Pokédex. Unlike the first three games of the generation, it is the fourth option seen after pressing "Start" at the title screen. This is because an option for connecting to the Pokéwalker is added directly after the "New Game" option. -Bulbapedia
So here are the steps:
1. Get the PokeDex
2. Go to the fourth option seen in the Start menu (after pressing Start)
3. Get your gift.
(Note: You need WiFi)