How is a perpendicular angular momentum origin in gyroscopic precession? 
Assume in the given diagram, $\theta = 0$, for sake of simplicity
Then, I understand there exists an initial angular momentum in the y-direction and a torque in the X direction of the gyroscope. This causes the angular momentum to chase the always perpendicular torque and hence it precesses a circle. However, this rotation in the yx plane gives it an angular momentum in the z-axis that did not exist before, and to my understanding, no torque acted on it to make it so. Where does this angular momentum come from? What applies the torque needed for this?
Thanks!
 A: It sounds like this question is related to another one, although you're not specifically asking about energy. As you said, the torque along the $-x$ direction is perpendicular to the angular momentum along $y$, and those two will remain perpendicular, so the gyroscope precesses. 
It appears you answered your own question: there is just a single nonzero torque acting about the pivot point, due to gravity and initially along $-x$. If you see this situation happening physically you'll notice that the center of mass of the gyroscope drops a little bit as the precession begins -- this sag causes the angular momentum from the original rotation ("spin") to gain a downward component, equal and opposite to the angular momentum gained from the precession. 
(Note: the sag decreases potential energy, so it also explains how energy is conserved in the presence of precession.)
One way of thinking about the sag is with forces: there's no support force at the center of mass, so there must be some drop from the initial height before the gyroscopic motion catches it.
I hope this helps!
A: When the torque is applied the initial response is that the center of mass yields to the torque (very briefly). That is, the first (very brief) response is that the center of mass moves in the same direction as in the case of a non-spinning wheel  
The motion of yielding to the torque combines with the spinning of the wheel to result in the precession. The mechanics of that conversion process is described in an answer that I wrote in 2012, discussing the start of gyroscopic precession. 
The process of initially yielding to the torque (very briefly) has been experimentally confirmed by Svilen Kostov and Daniel Hammer. Article: 'It has to go down in order to go around'.
The reason I mention the experimental verification is that there is a widespread assumption that gyroscopic precession is something that happens instead of yielding to the torque. Kostov and Hammer have verified the way that gyroscopic precession actually starts.
