The location of the dagger varies, there's no set dungeon for it. The first step in the quest should indeed be to find the dagger, so I'm not sure why you wouldn't have an initial objective telling you to find it and a quest marker on the map showing its location.
UESP says that "possible dungeons include http://www.uesp.net/wiki/Skyrim:Forelhost, http://www.uesp.net/wiki/Skyrim:High_Gate_Ruins, http://www.uesp.net/wiki/Skyrim:Lost_Valkygg, http://www.uesp.net/wiki/Skyrim:Ragnvald, http://www.uesp.net/wiki/Skyrim:Valthume, and http://www.uesp.net/wiki/Skyrim:Volskygge" and the discussion there seems to come to the conclusion that the Fang will always be located in a Dragon Priest's lair. It's possible to find the Fang before ever getting this quest, so my guess would be that its location is determined when you start a game and not generated when the quest activates.
Is it possible that you went to any of its potential locations earlier and picked it up, or didn't realize it was there and left it? Altho if it wasn't in your inventory at all, I would think that would cause the game to give you the objective to find it before advancing you to the next objective.
Wish I could be more help, I've found the Fang once but never actually done the quest that requires it.