The first time you encounter Entei is *completely luck-based*. You can speed up that process by using the method described above by An Asocial Moth. After encountering it for the first time, it will appear on your pokedex, including its current location (which changes with each cutscene). You can then use the same method to encounter it again, but it will be easier as you'll know its precise location.
This goes for all three roaming legendaries. Also note that they'll use a move like Roar/Whirlwind to instantly end the battle, so your lead pokémon must be faster and must use a trapping move like Mean Look to have a chance at capturing them.