You have to complete the entire Legion class hall campaign all the way up through recruiting your Legionfall champion on each class to access the mount quest chain, and is most likely what they mean by the Legion campaign. Much of the breaching the tomb can be skipped over otherwise, although you still need to do the first two parts (escort Khadgar, scenario can be skipped). Once you’ve done the class hall campaign, Maiev should offer the questline to recruit your legionfall champion. After that, the person that offers the mount quest should appear at the Broken Shore camp.
If it seems like you’re missing something and don’t see a quest you need on Broken Shore, don’t forget to do the “A Hero’s Weapon” quest to empower your artifact in the class hall (shown at the end of each campaign in the link below).
Editing to add links: