I am playing a paladin in the first scenario (level 3) and I have read that taking 4 levels of fighter would be beneficial. When do I take these, is there a particular schedule? Also, is there another class that would multi-class well? I am curious about what other multiclass combinations work well.

Yes, FTR levels work very well, as you get 3 extra feats for 4 levels. This allows you to grab Weapon Specialization for the +2 damage bonus with your weapon of choice. You can take them whenever you want. Generally it's done relatively early in order to cash in on the bonus feats early though.

Other classes that mix well with Paladin are Champion of Torm, Monk (depending on how you build the character) and, to a lesser extent, Sorcerer (add some Red Dragon Disciple for the stat boosts and you can build a pretty kick ass character). Another one I love to mix with Paladin is Rogue, but many people take issue with that from a roleplay perspective (I don't).

Actually I wouldn't multiclass a Paladin at all, unless you maybe go cleric for the remainder of the game, having pretty potent fighting ability from the paladin levels. But even then, already having 3 levels is almost too much for a base.

While fighter levels usually grant a big bonus for the fighting ability besides a few feats (4th level weapon specialization is particularly great) a Paladin already has just as good baseline fighting skills as a fighter.

More to the point, paladin gets a bunch of special abilities and divine spells going up levels. Taking fighter levels seriously nerfs this.

Paladin is one of the classes that's best played pure-class.
(Essentially a fighter/cleric multiclass with a fancy name.)
I'd only multiclass one for roleplaying purposes, not to make the character stronger.

I always find Paladins too feat starved for my tastes and their spell list is... not that great, so I rarely worry too much about relying on casting spells with them. Champion of Torm abilities that overlap with the Paladin's will stack as well (i.e. Lay on Hands and Smite Evil).

Thank you, I chose a weapon specialization (bastard sword) at level one. The whole multiclass thing is really interesting and all of the combinations are a bit overwhelming. The Paladin is my favorite class, so wanted to play it first. The prestige classes for SoU and HotU look sweet.

Yeah, few feats, few abilities, few skill points and few spells. (Not particularly well suited for my play style.)
The buffs are pretty neat though and compliment a holy warrior well.

All the more reason to go pure paladin if you go paladin. Mix in the fighter levels and you'll pretty much have a less powerful fighter with few low level spells. Stay pure and 3rd and 4th level divine spells can really make a difference (and have better saving throws too).

I agree about the Champion of Torm though. It compliments Paladin very well, but you should only start grabbing those levels later on, when you already have 10 or so paladin levels (wont meet the requirements immediately anyway).

Actually now that I think of it, Paladin/Champion of Torm should make a pretty darn great combo. Saving throws through the roof!

---
This is what I love about the game. So very many ways to go about building your character.

Just a note: that would be either Exotic Weapon Proficiency (required for Bastard Sword) or Weapon Focus:Bastard Sword (which grants a +1 bonus to hit with the weapon).

Weapon Specialization is a different feat, which is only available to the Fighter class.

I I added both Exotic Weapon proficiency and Weapon focus- bastard sword as feats.

Oh yeah, one more thing you probably noticed already.
Once you've multiclassed out of a paladin, you can't take paladin levels anymore.
But the best paladin stuff comes in the first 3 levels anyway...

Unless the module he's playing has custom scripting to prevent it, yes he can. The default rules of the game don't prevent taking Paladin levels, switching to another class, then taking Paladin levels again. As long as his alignment doesn't shift away from Lawful Good he can switch back and forth as much as he pleases.

DON'T DO IT! Paladin's are a great class by themselves and are not meant to multiclass!

Oh, right, NWN section. I'm playing Temple of Elemental Evil again right now and sort of...

uhm a paladin/ rogue ;p

After reading some of the posts, I am not going to multi-class. The paladin really is a fighter/ cleric after all. We'll just see how it goes. I just completed the peninsula district and have Tomi Undergallows as my henchman. So far, so good. There are just so many options and i just want to kick some serious butt. The game is really excellent.