I like "Rodney Yee's A.M. Yoga for Beginners". It is gentle enough for when you're just getting started and only 15-20 minutes. It doesn't feel like much, but after several days you'll start to notice more flexibility. I start here whenever I've stopped exercising for a while.
Simply: Stretch every day, morning and evening or even more often. Start with physical therapy type exercises and then gradually add stretches from ballet, gymnastics, wrestling, etc. It'll put a literal "spring" in your stride, improve posture and range of motion, and lower perceived pain both during exercise and at rest.
The weights also improve flexibility but not in as balanced a fashion. Stories abound of lifters with the posture of a gorilla.