In total, there are fourteen legendaries that can be obtained without cheats or events in HeartGold and SoulSilver. Mewtwo, Zapdos, Moltres, Articuno, Suicune, Entei, Raikou, and Rayquaza can be found in both versions of the game. Post-game Lugia, Kyogre, and Latias are only available in HeartGold. Post-game Ho-oh, Groudon, and Latios are only available in SoulSilver.
Most of these Pokemon are found somewhere in the overworld and can be battled by speaking to them. However, a few are roaming legendaries; once unlocked, they run around the region and can randomly be encountered in long grass. Remember you can always trade to get Pokemon not available in your version.
Get advice on how to prepare...
...or learn where to find them.
Whenever possible, save before you battle a legendary. If you make a mistake - for example, your entire team is knocked out, or you accidentally faint the legendary - you can turn the game on and off to try the battle again, or better, soft reset. Soft resets restart your game without turning your DS on and off. To soft reset, hold L, R, Select, and Start. You will automatically return to the title screen, but you will lose any progress you made if you don't save beforehand. This is desirable for our purposes, because the legendary Pokemon is regenerated with different characteristics, such as natures, IVs, and shininess once you reboot your game, allowing you to reset for the exact Pokemon you want.
Secondly, pay attention to how many moves the legendary has used; in-game the number of uses each move has is referred to as PP. A move can't be used if its PP reaches zero. Once all of a legendary's moves run out of PP, it will be forced to use Struggle, which deals ΒΌ of the Pokemon's max HP as recoil damage. There is a good chance the legendary will knock itself out once it reaches that point. When this guide refers to PP, it refers to the total amount of PP a Pokemon has available to it.
Though roaming legendaries (Entei, Raikou, Latias, and Latios) move randomly, you can check where they currently are on the Pokegear's map, and your movements will also affect their location. A roaming legendary moves whenever you move to a new place, such as a town, route, or cave. The only exception is when you go to one of those places by travelling through a route gate - so don't use Fly to get closer to the legendary!
Once you're in the same place as the legendary, this is an easy way to get battling them. Place a Pokemon with one level less than the legendary at the front of your party. Next, travel to the route where the legendary is, use a few Super Repels, and walk through the grass. The next encounter you have is guaranteed to be the roaming legendary.
But encountering it is only half the battle (pun not intended). All roaming legendaries will attempt to flee the moment you encounter them. To prevent this, bring a Pokemon with the ability Shadow Tag (such as Wynaut) or Arena Trap (such as Trapinch or Diglett); another option is to bring a fast Pokemon which knows Mean Look. Finally, if you knock out a roaming legendary, defeating the Elite Four will get them roaming again, which is also how you can reset for natures, IVs, and shininess; those are regenerated each time the legendary is revived.
HeartGold and SoulSilver actually let you capture the other legendary for once. Ho-oh and Lugia both have 40PP and appear at lv. 70.
These Pokemon are unlocked during the main game's story. When you enter the Burnt Tower in Ecruteak for the first time, a short cutscene of them running away will play. They have a habit of doing that when you encounter them, too - they're roaming legendaries.
Suicune has to be spotted in six locations before it reaches its final resting place. In order, these are:
All of these locations are visited during the main story. Suicune will stop moving once it reaches Kanto Route 25 and will allow you to catch it. If you knock it out, you can find it again at the Burnt Tower. Suicune is lv. 40 and has 90PP.
To unlock them, get all sixteen badges.
All three Pokemon will be found at lv. 50.
Once you have all sixteen badges, a lv. 70 Mewtwo will appear inside Cerulean Cave. You will need Rock Smash, Surf, Rock Climb, and Flash to reach it. It has 60PP.
To unlock them:
Latias and Latios appear at lv. 35.
To unlock them:
Groudon only has 30PP, while Kyogre fares slightly better with 40PP. Both appear at lv. 50.
To unlock Rayquaza:
Rayquaza has 50PP and is lv. 50.