Diagnosing extinct species is even more difficult than extant taxa (see this question). Because systematists describing fossil species (usually) only have skeletons, they compare to other fossils. You are correct that diagnosing a species from only a skeleton can be tricky. What defines what you call a genus, a species, etc.? How morphologically *dis*similar can two skeletons be before you call them different species? The running joke is that if you found fossils of a chihuahua skeleton and a great dane skeleton, you would certainly call them different species. But by modern biological species concepts, they are the same species. Then there are extant species that are essentially indistinguishable in terms of their skeletons, but do not interbreed, and so are probably different species.
Sometimes there is consensus, and sometimes there is not. This disagreement can lead to a description of a new species by one person being reclassified ("revised" is the term used) as another species. There are lots of examples of this among dinosaurs. Most famously, Brontosaurus was revised as actually being Apatosaurus. More recently, and relevant to your question, Nanotyrannus is thought by some to be a juvenile Tyrannosaurus rex.
So then how did Fiorillo and Tykowski, who described Nanuqsaurus hoglundi, decide that it was (1) not just a juvenile T. rex and (2) that it was a new species? Their rationale is laid out really well in their paper, primarily in the sections "Diagnosis" and "Description". You are rightly picked out the two questions that paleontologists reading this paper would want to know.
Nanuqsaurus is not a juvenile:
The dorsomedial edge of the maxilla is marked by deep pockets separated by pronounced transverse ridges. These together formed a strong peg-in-socket articulation between the dorsal margin of the maxilla and the ventrolateral edge of the nasal. The same kind of deeply interlocking naso-maxillary contact is a well-documented character that is also present only in developmentally mature individuals of the derived tyrannosaurines Daspletosaurus torosus, Tarbosaurus bataar, and Tyrannosaurus rex 2, , , , . The nasal-maxilla contact is either smoothly grooved or bears only weak scalloping in immature individuals and more basal tyrannosauroids 2, . The presence of this feature in DMNH 21461 is evidence that the material also represents a developmentally mature individual.
What they are saying here is that maxilla (part of the front of the upper jaw) in Nanuqsaurus has a very characteristic relationship to the nasal bone in which they form a peg-and-socket joint. This relationship is found in tyrannosaurine dinosaurs like Tyrannosaurus, Daspletosaurus, and Tarbosaurus. But more importantly, it is only found in adult tyrannosaurines. So they conclude that Nanuqsaurus is an adult.
Nanuqsaurus is a distinct species from Tyrannosaurus and other tyrannosaurines
In all three hypotheses of phylogeny, Nanuqsaurus hoglundi was found to be a derived tyrannosaurine, the sister taxon to the Tarbosaurus+*Tyrannosaurus* clade (Figure 6). This node was supported by a single unambiguous character, the presence of a dorsoventrally tall, paired sagittal crest on the frontal. The age of Nanuqsaurus hoglundi (70-69Ma) is consistent with its place in the recovered hypothesis of tyrannosauroid phylogeny, positioned in time between the more basal Daspletosaurus torosus (Middle to Late Campanian) and the more derived Tyrannosaurus rex (latest Maastrichtian) among other North American tyrannosaurines.
The authors ran a phylogenetic analysis of characters coded for Nanuqsaurus and about 20 other taxa. Nanuqsaurus has enough shared characteristics to put to solidly among tyrannosaurine (near Tyrannosaurus, Daspletosaurus, and Tarbosaurus). But, importantly, it has a characteristic that none of these others have: "the presence of a dorsoventrally tall, paired sagittal crest on the frontal.
Based on its being an adult and having a character that is not found anywhere else among tyrannosaurines, Fiorillo and Tykowski name a new species. I'm simplifying what they did, but that's the general idea. To their credit, they acknowledge that there is not a lot distinguishing the new species and discuss in much more detail their rationale and the implications of their results.