Yeah. After you released them from the Burned Tower, and after you beat the E4, THEN you can look for them. Even though Johto is big, just don't give up. I suggest having Repels/Super Repels/Max Repels while you're searching. Why? Well, the Legendary Beasts will be at lv. 40 if you find them. If you put a Pokemon who is lower than lv. 40 (I suggest lv. 39) in the first slot in your team and use a Repel item, every wild Pokemon who has a level LOWER than the Pokemon in the 1st position won't appear. That cuts down on those Pidgey that you don't want to look through! Once you find a Legendary Beast, it will run from you, but you will have the data in your Pokedex so you can see where it is every time you move from route to route. Heh. Use False Swipe to battle them!
*whew*