How should I teach someone new to spades how to bid?
Turn them loose with a computer simulation at first so they can get lots of hands in. Only after seeing the general structure of play will they understand what to even consider when bidding.

I suggest a computer simulation as it means you don't have to spend time playing with a completely clueless person and they can learn on their own. If you situation is amenable to new people and lots of hands, then just plain old playing a bunch is the answer.