Companions in Fallout 2 level up with you, but what if they are put on hold and then recruited again? Do they gain levels automatically to match my own or do I have to level them up?
No they don't.
They level at random* approximately every 3 levels but they only have a chance to level up if they are in your party when you level.
*The chance is based on how long since they last leveled so you they level at least +1 for each +3 you do, but only if you have them with you.