When I got a fatty into shape, I started out with walk and trot for half an hour, twice a week. After a couple of weeks, I introduced the canter on large circles and for short spurts. I increased the riding to three days around the same time that I started increasing the lengths of our rides. Now I ride him four days a week for 45-60 minutes. Basically, don't push Romeo further than he can go, build up the workouts gradually, and take your time in cooling him off/warming up.
As others have said, hillwork is great for building up those hind quarter muscles! Back when I had access to hills, I'd try to do hillwork once or twice a week. I would warm up my horse then walk and trot up the hills, keeping her in a working frame the whole time and pushing with her haunches. We never did much cantering or galloping up as trotting seemed to work the best for us.