So I've finally caught all the Legendary Pokemon. So I'm gonna post where they all are so that way people know for future reference. I'm gonna divide the Legendarys into 3 classes: Before Elite 4, Rock Smash Legendarys, and Eve Cave.

Before Elite 4

Deoxys- After watching Mewtwo and Deoxys battle each other and you beat the Eighth Gym Leader (Professor Oak). Head to Tekor Island. Enter the bottom house on the island where you'll see a sailor. Talk to him and ask him to send you to birth island. This is where Deoxys is. Ultra Balls work on him.

Mewtwo- Fly over to Spear City, move south, and enter the cave. Climb down the latter and head east (or right) until you see a body of water. Surf and climb the waterfall and enter the little cave up top. This is where Mewtwo is. Ultra Balls can work on him.

Celebi- When heading to the Pokemon League, keep heading west (or left) until you can't surf anymore (it should be Route 38). Head North (or straight) until you land. You'll see what appears to be a forest that you can enter. This is where Celebi is. Ultra Balls work on him.

After Elite 4/Rock Smash Legendarys- After beating Elite 4 head back to the town before pokemon league. Talk to the scientist and he'll give you Rock Smash. This is what you'll use to get the Legendarys that require Rock Smash.

Raikou- Fly over to Pokemon League building and head south. Go through the second cave until you find 2 Rock Smashable boulders next to each other with a pathway above that. Rock Smash both boulders and enter the cave to unlock Raikou. Ultra Balls work on him. WARNING: He knows Roar and I don't think you can get him if he Roars you out of combat. Use F2.

Entei- In between the first and second cave when heading to the Pokemon League building. There will be a 2 Rock Smashable boulders next to each other with a pathway above that. Rock Smash both boulders and enter the cave to unlock Entei. Ultra Balls work on him. WARNING: He knows Roar so follow same procedure as Raikou.

Suicune- Fly over to  Tekor Island and head to the spa cave (Lipton Chamber) on the way to the Eight Gym Leader. Don't enter the cave. Surf around the little island until you see a Rock Smashable boulder. Rock Smash it, use surf, and head straight till you see a peice of land. Land, head straight and enter cave to Unlock Suicune. WARNING: He knows Roar so follow same procedure as Raikou. This is also the area where Unkown are.

Mew- Head over to Crater Cave (not from the Bronx side). Rock Smash the boulder you see in the cave to unlock the path were Mew is. Ultra Balls can work on him. WARNING: He uses Transform at the start of the battle.

Lugia & Ho-Ho- Fly over to Therus City and head southern end of the city. You will see a Cuttable plant with some water that is surfable. Cut the plant down, surf the water, and head west (or left). You will see a cave that was once blocked by an old woman. Enter the cave and complete the little puzzle to unlock Lugia & Ho-Ho. Ultra Balls can work.

Moltres- While near Therus City, head east (or right) and enter the cave that has all the Fire pokemon. Rock Smash the first boulder you see and follow the path. This is where you get Moltres. Ultra Balls can work.

Zapados- Head over to Nemu Town and surf until you reach Steele Cave. There you will find a Rock Smashable boulder. Rock Smash it to unlock Zapados. Ultra Balls might work.

Articuno- Head to Frosty Cave. Rock Smash the boulder you first see to unlock Articuno. Ultra Balls might work. After you catch Articuno DON'T LEAVE.

Eve Cave- While in Frosty Cave you will solve some puzzles to unlock a pokemon battle with the creator of the hack. Defeat him and he'll unlock Eve Cave. Head to the first town that you visited (the one where the guy kicks you off the property and east of the starting town). Head south, find some Cuttable trees, and enter the building you see. Talk to the girl and she'll transport you to Eve Island. But you can't capture the rest of the Legendarys yet. First get a Salamace, have it in your party, head over to Lipton Chamber, and talk to the old lady their. She'll die after finally seeing a Salamace (it was her last wish). Head back over to where the house where the girl will transport you to Eve Island, head straight and talk to the old woman who is blocking the enterence. She'll let you into the cave if you completed the prevous steps. Here you will find:

First Floor- Regice, Regirock, and Registeel.
Second Floor- Latios, Latias, Kyorge, Groundon, Rayquasa and Jirachi.

FRENDLY WARNING: WHEN I SAY ULTRA BALLS MIGHT WORK I MEAN THAT THE POKEMON IS IN THE RED AND HE HAS BEEN PUT TO SLEEP.

And Congradulations you have caught all the Legendary Pokemon in Pokemon Fuligin!!!

Edit: The Mew in this game seems to disobey your orders. So maybe try to use a Luxery Ball that promotes friendlyness. I've been leveling him to see if he will obey...so far no luck.

Re-Edit: On my second playthough Deoxys disobeys me. So expect that some Legendarys to disobey you (might be a bug as all pokemon should obey you up to the point). I would requiemend that you F2 save before you do battle with the Legendarys, catch them, send them out to battle, if they obey you then no issue.

If they disobey you then F4 back to the point before you battle and re-capture.