Could be an unfinished roux (the butter, flour mixture).
But most likely it's because the cheese was heated too quickly or too much, causing the protein to clump up.
Suggestions: Melt with less heat Use a double boiler (to reduce hot spots within the pan)
Toss the shredded cheddar with cornstarch first (starch helps reduce clumping)
Add cheese in smaller batches (easier to maintain correct heat level and stir cheese in)
cooking.stackexchange.com/users/649/Tim Gilbert
In my experience it's because of: too much heat too much acidity (for example from a shot of lemon juice)
Too much heat causes the protein in the cheese to clump.
You can use a mixer to dissolve the clumps (mix at the highest speed).
Too much acidity also does the same.
The more sour a sauce gets the faster it clumps when heating.
Lemon juice gives a nice flavour but it's finnicky.
When the sauce clumps you can save it somewhat using a mixer.
cooking.stackexchange.com/users/1377/nalply
I have two suspicions: One, you're undercooking your roux, the flour and butter mixture, and not fully incorporating the flour.
Two, you're adding too much cheese too quickly and it isn't melting smoothly.
Solutions: cook the roux until light golden brown, finely grate the cheese and add it slowly, stirring constantly.
cooking.stackexchange.com/users/1443/Ocaasi
I've run into this problem the first few times I made macaroni and cheese from scratch.
Things that I've learned are: don't use low fat milk --
the higher the fat content the smoother your cheese will melt/incorporate.
once the base is made (the flour, butter, milk "sauce" -- bechamel?)
take the pot OFF the heat.
The more your heat your cheese sauce, the more it will get gritty.
if possible, mix with a good melting cheese -- to make my cheddar sauce, I use 1 part moteray jack (which has no taste (IMHO) but is a really good melting cheese) to 1 part sharp or extra sharp cheddar cheese.
Hope that helps.
cooking.stackexchange.com/users/5958/Macromika
Three other possibilities are: If you used pre-shredded cheddar it's sometimes dusted with an anti-caking agent which can make things tricky.
Your cheddar is a reduced fat cheese which doesn't have enough fat content.
The flour you are using for your roux shouldn't be a whole wheat/whole grain.
You can cook that down and it still won't be as smooth or finely integrated as using an all-purpose flour.
Hope this helps.
cooking.stackexchange.com/users/6844/Megan
Good cheddar has little chunks of calcium lactate on/in it - could it be that?
cooking.stackexchange.com/users/1610/Rich
At Modernist Cuisine, they wrote: Cheese is an emulsion of dairy fat and water, but that emulsion tends to break down when it gets hot.
The starch particles and milk proteins in béchamel act as emulsifiers, but they aren’t very good at their job and result in poor flavor release. ... ...
Sodium phosphate keeps the water and fat droplets mixed when the cheese is melted.
We use sodium citrate, which has the same effect and is easier to find.
The resulting texture is as smooth as melted American cheese, but as complex and intense in flavor as any of your favorite cheeses. and watch this video .
cooking.stackexchange.com/users/19442/Nate
I can think of a few reasons why you may be getting this grittiness.
I use the following method when making cheese sauce, and it tends to turn out very smooth.
Melt (hard) butter in pan at a low temperature.
Add the appropriate amount of flour.
(Better too little than too much, as adding more later should not hurt.)
Whisk the butter-flour mixture quickly to create the roux, still at low temperature.
(10 - 20 seconds)
Add the milk and whisk quickly, mixing in the roux.
Turn the heat up immediately and continue whisking.
When the sauce is sufficiently thick, reduce the heat and add in the grated cheese.
Stir until smooth again.
cooking.stackexchange.com/users/1123/Noldorin
I have found that adding gradually adding flour to the butter using a sifter reduces the likelihood of a gritty texture.
cooking.stackexchange.com/users/246/Laura Kane-Punyon
Many of the other answers are good, but I still often have the same experience with certain cheeses such as cheddar
(it's 'smooth', but not as smooth as I would like).
If the proportions are reasonable, a hand blender works for me every time.
cooking.stackexchange.com/users/30974/James
It's best to use half and half or whole milk.
Every time I use 2% milk it comes out separated and grainy/gritty!
I guess it has something to do with the fat content that gels it altogether!
cooking.stackexchange.com/users/41460/Mae
Sometimes when making a very simple cheese sauce (butter, flour, milk, cheese [cheddar, usually]), the final sauce has a sort of gritty or slightly pebbly texture (rather than smooth) - it seems like maybe the cheese hasn't totally melted, even if I continue to heat the sauce.  Why does this happen? How can I avoid it?
Why is my cheese sauce gritty?
cooking.stackexchange.com
<sauce><cheese><roux>
cooking.stackexchange.com/questions/4073
cooking.stackexchange.com/users/1532/SarahVV
It is possible that the cheese was heated too quickly or not added gradually enough to allow it to melt smoothly. Another possibility is that the roux is undercooked or the flour is not fully incorporated. Use a white flour for the roux and gradually add it using a sifter. Use half and half or whole milk and avoid pre-shredded cheese, as this contains an anti-caking agent that can affect the texture. If the sauce is still not smooth, a hand blender should help. The cheese should be add slowly and not heated too fast. Try sifting the flour and adding it bit by bit. Make sure your cheese doesn't have an anti-caking agent. You can also try mixing with a hand blender.
The cheese was heated too fast. The roux is undercooked or the cheese was added too fast. Try sifting the flour first. The cheese may have an anti-caking agent or calcium lactate. Try using a hand blender to mix.