As with all Pokémon games, Legendary Pokémon are a much coveted thing, and they appear in this game. While a couple such as Mew or Phione will be roaming around the stages, most Legendary Pokémon are bosses that can only be obtained in the rarest of circumstances. They will appear when you have three stars on the stage and get access to the Special area of it.
These do appear randomly, but you are more likely to find them during a Fever, especially a Super Fever, so when you see the rainbow, plan your travel accordingly.
These Pokémon, like all Boss Pokémon, have a low drop rate when you do battle them, so many will require multiple trips. If the Legendary Pokémon has alternate forms, like Landorus, Arceus, Deoxys etc., then the form you face is random. As there is a special title for collecting all the forms, you will have to have multiple attempts at capture.