Riding trainer doesn't have cold weather flying listed

I'm playing in the icecrown server, as a level 73 orc shaman.

I already bought the riding training to be able to use flying mounts, but to use them in northrend i need another skill/training. But for some reason the npc that would be selling it (the riding trainer at warsong hold) doesn't even have it listed, which is weird since i've seen lvl 70 players using flying mounts, so technically i should be able to learn it.

Am i talking to the wrong npc or do i need to do something else before that too?

You can fly early as level 68 in Northrend. If you have level 80 character that you used to buy Tome of Cold Weather Flying from Dalaran.
For first time levelers you have to wait to level 77 to be able to buy fly training in Northrend.

Oh, didn't know about that detail, thanks for the help!