I imagine they'd need to be much larger than any extant cat (like ligers, Panthera atrox, or the ginormous cat mounts they have in World of Warcraft) and need more rigid spines, longer legs, and more giant shoulder blades. This would all result in a cat that is markedly un-feline-like, as they all IRL have the general same body plan -- flexible spines that would bump the rider up and down a lot if they were being ridden, for instance. And then I can't even begin to fathom how the difference in shoulder blades would change the overall appearance. Also, they'll probably have to be omnivorous unless their riders have an insane meat industry available. There's no way around these changes other than handwavium "it's fantasy, shaddup," I'm guessing. I don't wanna do that. I want them to be scientifically explainable, even if that means having a strange-looking yet very practical kitty. No, I won't accept answers like "the thing you're looking for is horses or large canids" because dang it, I want a cat mount.
There are numerous things that prevent cats from being good mounts. Overall, this would require genetic splicing or some extreme breeding selection, but I can't imagine that it would come about in the wild.
The primary problem isn't structural so much as metabolic. Cats are tuned for slow, lazy slinking followed by occasional bursts of speed. This means no cross-country cat-back rides. If you change that, then what you actually wind up with is a wolf, not a cat.
But let's presume you want a steed that sleeps in its kennel/cage/wagon most of the time, and you only pull it out for combat.
- Cartilage supported spine improves flexibility, but makes for poor load-bearing. Similarly, a shorter torso would be beneficial.
- Claws would have limited use for this creature. The whole "pounce" thing would make it tough to stay mounted.
- More rigid limbs would be required to discourage it from rolling all the time. Rolling is a standard cat combat behavior, and having an 800lb cat roll over you isn't conducive to being able to get up and fight again.
- Tougher paws to handle rough terrain when the steed can't pick its way carefully over a space.
Overall, while it looks cool, cats's fighting style just isn't conducive to being ridden. They tend to want to use their front claws to grab things, and their back claws to rake things while the teeth bite into it. Whatever you wound up with as a cat-mount would only look superficially like a cat.
Well I can help on how they get big. There is two ways I see plausible.
Cats had been fighting other cats or creatures for a long time and the bigger cats were more likely to survive. So bigger is a favorable trait so it gets past down by natural selection.
Breeders breed cats to be bigger by have the larger cats breed each other until they are a desirable size.
Now on fact on appearance, not much will really need to change except bones for legs will need to be thicker and the proportions will be different to like long limbs and and bulkier build. You also mentioned that you think they should be omnivore. This is a good idea to have it just will change the autonomy of the cat will change greatly the way that the cell function will change, their intestines need to be longer and their back teeth need to be more flat like dog back teeth.