i introduce them as needed. without having put the thought behind it, in my WIP one of the main side-characters isn't seen until halfway through, and not even hinted at because the protagonist doesn't know he exists just yet. it's the only story i've ever done, i think, where the point of introduction may be a source of contention with readers. instead, there's just a hint earlier about this alternate way of life, but beyond that there's nothing. when the protag discovers these people, that's where the book runs off a cliff, hopefully in a good way.
it's rather like life, eh? i mean, you *hear* about people all the time, and sometimes you come to meet them in person. others just pop in out of the blue, depart something or take something away, and you never see them again. from a dramatic standpoint, it's probably usually best to build the character's arrival up with some foreshadowing or drop a hint. then again, not knowing the sidekick has a sister who just drops in from the sky can work well, too, if that's the dramatic element you're shooting for.
but, rules? probably nothing written in stone, rather some techniques are better than others, and even then it probably greatly depends on the situation. for example, how many seasons did it take to get to know 'the smoking man' in the 'x-files' show? he was always around, though. on the flip-side, seems that one staple of romance writing is introducing the male through his reputation, creating a whole instant profile for the reader, upon the first time the chick sees him from across the room. 'she saw that raif wellington mingling with the prettiest of women, confirming what rachel had always heard about him being a womanizer. she decided to steer clear of men like that... but his eyes demanded her attention.' (pretty bad, huh? lol.)