It depends upon the spell. Spells without somatic components can be cast just fine while holding a weapon and a shield. So those few spells (Blindness/Deafness, Holy Word (IIRC) and a few others) and Stilled spells are just fine. Otherwise you need a free hand. (IME, clerics are indeed the most likely characters to overlook this. Paladins are usually pretty good about it as are fighter/wizards and bards).
So, how do clerics deal with it? The cleric I'm currently playing wields a greatsword so it's not too much of a problem. He just lets go of the sword with one hand, casts the spell, then puts his hand back on the sword. That's never caused any problems (although a clever foe might exploit it by trying a grapple check or something while he's not wielding the sword). Most DMs let characters switch grips on a weapon at will (for instance, attack with the bastard sword one handed in round one and then switch to two hands when you start power attacking in round 2)--and those who don't generally let the cleric spend an MeA to do so. (Which I think is silly myself--after all, it's an MeA to pick the weapon up off of the ground or to draw it from its sheath; it should be a good deal easier to just put a hand back on it. And I've never seen any DM question how wizards are wielding their quarterstaffs while casting spells).
Other good routes would be wearing a buckler and simply casting with the buckler hand (which still counts as a free hand) or wearing a light shield and holding the weapon in the shield hand while casting. (Which may or may not constitute a move action depending upon the DM).
Another route that I've seen clerics use is simply to walk around with their weapon in the sheath. Wear a spiked gauntlet so that you still threaten but cast your spells before you move into combat. Quickdraw might make this route even easier for the battle cleric.