As I don't recall seeing a guide like this before, I thought that I'd like to share some really helpful info.

You know how you gain access to the Cerulean Cave (and ultimately Mewtwo) after linking PC's with Lanette? Well, you also unlock one of the three Legendary Beasts, depending on your starter.

Charmander gets Suicune, Squirtle gets Raiku, and Bulbasaur gets Entei.

Now the hard part: catching them.

You don't need the MasterBall to do it if you've got a Wobbuffet/Wynaut to battle it with, but that takes a VERY long time and is VERY risky.
It's also expensive, since you'll end up having to throw many Balls at it.
I know, since I had to catch my first Suicune that way.
So, if you don't have your MasterBall, you should stock up with Timer Balls (and some Net Balls if your Legendary Beast is Suicune) before continuing on.

Say you do have the MasterBall. Then what?
You need to have captured Mewtwo.
Now, when I say 'need', I really do mean it, since on ALL of my restarts on FireRed, the Legendary Beast didn't appear until I caught it. My friend has confirmed this on her copy of LeafGreen.
So if you haven't caught Mewtwo yet, go get it; but don't use your MasterBall.

Next, you need to know the location of your Legendary Beast.
While it may seem a bit hard to believe, yes, all three of them DO have a set starting area.
How do I know?
I have at least a dozen of each of the three Beasts sitting in my PC, and each Suicune, Raiku, and Entei was caught in the same place on FireRed, respectively. The same friend mentioned above has also confirmed this on her copy of LeafGreen.
So, to save you some hunting time, here's where they're found:

Entei is found on Route 4 (the area between Mt. Moon and Cerulean).
Raiku is found on Route 5 (the area between Cerulean and Vermillion, where the Day Care Man is).
Suicune is found in the water off of Route 10 (you need to Surf across it to get to the Power Plant).

Sadly, if the first sighting results in it running away from you, it will not appear in that area again (unless you 'chase' it there, of course).
However, it is now entered into your Pokedex and you can track it using the Location option.
Remember, if you end up having to chase it for another chance at catching it, it will move ONE area for every TWO that you do. So, for example, moving from Lavender Town to Route 8, then from Route 8 back to Lavender Town, your Legendary beast will move from its current area to one adjacent to it (excluding towns, buildings, and caves).
Just so you know, using Fly DOES count as walking through routes and cities. For how much, I don't know, since the Beasts enjoy hopping back and forth between Routes. So, if you can, avoid using Fly after your first sighting if it's close to your area.
And it IS possible to run into any one of the three Legendary Beasts on water.
It IS also possible to run into any one of the three while Surfing or walking in tall grass while in the area with the guards that check your badges before getting into Victory Road. I was pretty surprised when I saw Entei there.

Now, before you all yell at me saying that the first appearance is completely random, I would like to tell you that me encountering Suicune for the first time on several restarts and my friend encountering Suicune for the first time on her game is hardly a coincidence.

Neato guide, ourspunkyworld. I am borrowing a friend's FireRed and so far I've caught him all the Kanto legends with Ultra Balls! and I was just about to get him Suicune, thank you for the advice!

my suicune appeared next to nugget bridge, so maybe YOU found them there...

Also, i didnt have mewtwo untill after my suicune.