They are bred, but you're also correct that any given variety is all grafted from one original tree. Apples can be bred by cross pollinating varieties, planting the seeds, and then taking scions from the sprout and grafting them onto mature trees (sometimes with dozens of varieties of apple grafted to the same rootstock) so that they yield fruit faster. I think it's typical to go through about 1000 seedlings before you find a good apple for fresh eating (many more are good for cider though).

You can also just plant the seeds and let them grow naturally, but it takes a lot longer to get any kind of results (not to mention more space).

I'm just getting started on this process at my farm actually (apples, pears, asian pears, and cherries so far, seedlings are growing, but I haven't grafted scions yet). It's a major exercise in long-term record keeping.

Here's an example of a tree with a lot of varieties grafted to it, though this guy isn't doing it for breeding purposes: http://www.dailymail.co.uk/news/article-2437247/250-varietie...

Here's a wikipedia article that mentions the grafting process for testing new hybrids: https://en.wikipedia.org/wiki/Grafting

They bred them until they developed red delicious. Once they got it, they graft it onto rootstock.