Pokémon Gold and Silver: All Jotho Legendary Pokémon Guide made by TornadoMudkip.
I hope that this Guide is useful to read! Please enjoy this Guide/Walktrough!

First the Legendary Dogs: Entei, Raikou and Suicune. (Also known as the Legendary Beasts.)

What do you need to catch Entei, Raikou and Suicune?

~ A lot of Poké Balls like an Ultra Ball or a Fast Ball. (Fast Ball because the Dogs are really fast.)
~ A Pokémon with the move: Mean Look. (Pokémon with that move: Golbat and Haunter.)
~ A Pokémon with the move Thunder Wave. (Like a Mareep.)
~ A Pokémon with the move Sleep Power or Hypnosis. (Like Haunter or Hypno)

You can't catch them at the moment if you're in Ecruteak City. Each of these three Pokémon can appear later in the Game at a random place if you're in another area (Like a Route.). So it's just a matter of luck as you encounter them. This can take a long time and it may even be that you don't encounter, if you don't give up you can catch them for sure! Is it really 100% a matter of luck? Well, not quite. The place where these three Pokémon are located, you can directly look in your Pokédex/Map to see if there is one near you. The bad news is that it's very difficult to catch them. I'm now giving some Tips to catch them easy. (This actually worked for me on Pokémon Soul Silver, I caught Raikou with these Tips.)
All of the Dogs are at Level 40, Raikou is an Electric type, Entei is a Fire type and Suicune is a Water type.

If you encounter one of the Dogs, use your Haunter (Or another Pokémon) and use the move Mean Look or Hypnosis.
With this the Dogs can't run away, use now some moves until the Pokémon has only some HP left.
If you first used Mean Look, use now a move like Thunder Wave, with this the Dogs is paralyzed.
Try now to catch it, use Poké Balls like an Ultra Ball or a Fast Ball.
With these Tips you can catch every Legendary Dog easy. (Also goes for Latias/Latios in Ruby/Sapphire/Emerald.)

Second: Ho-Oh and Lugia.

If you play Gold you can catch Ho-Oh and later Lugia.
If you play Silver you can catch Lugia and later Ho-Oh.

What do you need for Ho-Oh?

~ A lot of Poké Balls like an Ultra Ball. (The best is if you buy 25 Balls or more.)
~ A Pokémon with the move Thunder Wave or Hypnosis.
~ The Rainbow Wing.

To find Ho-Oh, you must go to Ecruteak City. (City with the 4th Gym.)
If you're in the Bell/Tin Tower you must go to the top, this is a long way to walk but if you're on the top you can Battle with the Legendary Bird Ho-Oh.
If you are there: Save your Game first because if you lost against Ho-Oh or you did beat it, you can try it again.
Ho-Oh is at Level 40, which is really high, Ho-Oh is a Fire and Flying Type.
Ho-Oh is really strong, the best use on it is using Water Type moves like Water Gun or Surf.
Ho-Oh's signature move is Sacred Fire, which is really strong, so watch out!
If the Pokémon has not very much HP left use the move Thunder Wave or Hypnosis.
If you use that moves, it will be easier to catch Ho-Oh.
Use now your Ultra Balls and keep it up until you have Ho-Oh.

What do you need for Lugia?

~ A lot of Poké Balls like an Ultra Ball. (The best is if you buy 25 Balls or more.)
~ A Pokémon with the move Thunder Wave or Hypnosis.
~ The Silver Wing

To find Lugia, you must go to Cianwood City (City with the 5th Gym.) and surf to the east until you see the Whirl Islands, the place where Lugia lives.
Go in the cave, you must go to the place where Lugia is.
It's a long way but if you are there, you can catch the amazing Lugia!
If you are there: Save your Game first because if you lost against Lugia or you did beat it, you can try it again.
Lugia is at Level 40, a really high Level but for sure you can catch it.
Lugia is a Psychic and Flying Pokémon, many people think that it's a Water Pokémon because of it's Water moves.
The best use on Lugia is if you use Electric or Ice moves like Ice Beam or Thunder Shock.
Lugia's signature move is Aeroblast, which is really strong, so be careful.
If the Pokémon has not very much HP left use the move Thunder Wave or Hypnosis.
It will be easier to catch Lugia if you use these moves.
Use now your Ultra Balls and keep it up until you have Lugia.

Third the Legendary Grass and Psychic Pokémon: Celebi.

You can't get Celebi in Pokémon Gold and Silver but you can get it in Pokémon Crystal. (Only the Japanese Version.)

What do you need for Celebi?

~ A lot of Poké Balls like an Ultra Ball. (The best is if you buy 25 Balls or more.)
~ A Pokémon with the move Thunder Wave or Hypnosis.
~ The GS Ball. (You can get the GS Ball in an Event.)

Go to Ilex Forest and go to the Shrine and place the GS Ball there. (Save your Game first.)
Celebi will appear.
The best moves to use against Celebi are Fire type moves like Ember.
Also try to use moves like Sleep Power, then would it be easier to catch Celebi.
Use then your Ultra Balls until you have Celebi.

I hope that this Guide could help you a bit to catch the Legendary Pokémon in Jotho.
This Guide is also useful if you play Pokémon Heart Gold or Pokémon Soul Silver, because the most of the Pokémon that appear in that Game have the same requirements to catch. (Only the changes are that Suicune is somewhere else to catch and not running away and Ho-Oh and Lugia have now the Level 45.)
Have really much fun and enjoy your Game a lot!

wow this is wonderful! People who are stuck can come here for some info and help. I really liked this good job tornado

TornadoMudkip : Great walkthrough! Very detailed, and helpful for people who need help!

Wow, this is a pretty nice and well done walkthough, great job on this Tornado, nicely done. I haven't played this game for a very long time and I do want to play this game again since I seen this now..

Thanks all for your Nice Comments on my Guide/Walktrough.
Personally I think this Guide is my Best one until now. 

IgorBird122 : I hope that you play this Game soon again, it's is really fun to play!