Cheese can seize during cooking if heated too quickly - it starts to curdle, which is the clumping.
Try heating very slowly and gradually, adding a handful of shredded cheese at at time (shredding gives more surface area to melt quickly and more evenly). If you're using milk, use whole fat instead of skim or 2% - fat can help to stabilize the sauce.
Some cheese melt more easily than others, too - try a gruyere or emmentaler, for instance.
Are you making a good Béchamel sauce as a base for your cheese sauce? The sauce should be a good, smooth sauce before you ever ass the cheese. When you do add the cheese, make sure it is finely grated and add it a bit at a time, stirring to incorporate as you go. For the base sauce, add equal part of butter and flour. Cook it for a minute or two, but don't let it brown. Then, gradually add the milk (use ten parts liquid to one part roux), stirring all the while. Season with salt, pepper, and a dash of nutmeg. A pinch of cayenne or a dash of pepper sauce is a nice addition. Take it off the heat before you add the first bit of cheese. Stir until smooth, and put it back to the heat to warm up. Then add the next bit of cheese.
Just as a note, you don't want to bring either the white sauce or the cheese sauce to a boil as this can cause lumps, too.
Cubed cheese will incorporate better into your béchamel than shredded. When shredded, the protein strands are so shortened and chopped up that they can't incorporate as seamlessly as cubed cheese. Cubed cheese contains longer protein strands which, when relaxed by the warmth of the lovely sauce, can stretch out and take up moisture from the sauce, resulting in the velvety consistence you're looking for.
oops = ADD the cheese
I had the same problem until I used a whisk instead of a spoon to briskly incorporate the coarsely grated cheese. Gradual additions of cheese, lots of whisking, and voila! Perfect cheese sauce at last.
The term for the sauce described above is sauce mornay. Simply, it is cheese added to bechamel. no eggs required. And be sure to warm your milk to the scalding point before whisking it into the roux. Otherwise you risk having a lumpy sauce.
I thought the rule was add cold liquid to a hot roux and cold roux to a warm liquid. http://www.ibiblio.org/expo/restaurant/chef/roux.html
Has food science found this to be untrue?
Pierino is correct. The proteins in the flour in the roux will extend and take up liquid, be it milk or stock, much more efficiently and quickly if it is warm rather than cold.