To get Nat, you'll first have to unlock the garrison Fishing Shack, which becomes available at level 96. From there, your garrison fishing vendor will send you on a quest to catch a specific type of fish from a specific place. Once you turn that in you'll get a quest to go find Nat Pagle, and from there begins his recruitment questline. Once you complete all his requirements -- to fish up various Lunkers throughout Draenor using special bait -- you'll be rewarded with Nat as a level 100 rare-quality garrison follower. You'll also be able to start catching Lunkers throughout Draenor without using bait. No word yet on what Lunkers do, but my guess is that they'll be required for certain high-level cooking recipes, so devoted raiders or guild suppliers probably want to make sure to schmooze Nat into their garrisons! Happy fishing!