The companions can be met in various locations throughout the wastelands, best way to find them is hang out in bars or near town entrances, few of the best spots are:
NCR north spawn near Buster, NCR bars, Maltese Falcoon in Hub, Bar right in front of South entrance in Junktown.
You need 100 party points for each, having a high charisma should easily bring you one, boosting speech a little gets you 2 without too much of a fuss.
They are called travellers when you look at them, chilling in leather jacket/leather armor/metal armor with around 100-130HP w/o a weapon. You can learn the area of their expertise by talking to them, there are malee fighters, EW, SG, BG and throwers. What's important for the companions is the HP gain and base AGI, to check it get them a weapon and watch how they behave in TB, how many shots can be fired and look at the HP when they level. HP gain for companions works the same way as for players, 10EN - 5hp per level.