In Peter Jackson's film adaptation of The Lord of the Rings, we see Saruman as he takes the initial steps towards creating a new army. The orcs under his command proceed surprisingly quickly, and Gandalf later explains to Elrond that "Saruman has crossed orcs with goblin-men. He's breeding an army in the caverns of Isengard."
Later, when Saruman is speaking with Lurtz, he briefly relays the history of the orcs, and proclaims the Uruk-hai to now be the pinnacle of orc-kind:
Do you know how the orcs first came into being? They were elves once... taken by the dark powers... tortured, and mutilated... a ruined, terrible form of life. And now... perfected. My fighting Uruk-hai.
- Saruman, The Lord of the Rings: Fellowship of the Ring (2001) - The Fighting Uruk-hai
This all seems to suggest that the Uruk-hai are a new breed, and would likely be unfamiliar to the main characters. This definitely seems to be the case in books, where they only identify them as some type of orc:
And Aragorn looked on the slain, and he said: 'Here lie many that are not folk of Mordor. Some are from the North, from the Misty Mountains, if I know anything of Orcs and their kinds. And here are others strange to me. Their gear is not after the manner of Orcs at all!'
There were four goblin-soldiers of greater stature, swart, slant-eyed, with thick legs and large hands. They were armed with short broad-bladed swords, not with the curved scimitars usual with Orcs; and they had bows of yew, in length and shape like the bows of Men. Upon their shields they bore a strange device: a small white hand in the centre of a black field; on the front of their iron helms was set an S-rune, wrought of some white metal.
The Lord of the Rings: The Two Towers - Chapter I: The Departure of Boromir, pp.17-18
In fact, to my recollection, the term "Uruk-hai" wasn't even mentioned in dialogue until the Battle of Helm's Deep (specifically, in Chapter VII: Helm's Deep, on p. 145; and please note that I am referring to the dialogue, so the title of Chapter III doesn't count here).
But, in the film adaptation of The Two Towers when the trio meets Éomer, Aragorn refers to the horde they're following as "a party of Uruk-hai" (and earlier, Legolas told the others that "the Uruks turn northeast... they're taking the hobbits to Isengard!").
How did they know what they were called?