High stepping in rock climbing
To high step, you need to lift your knee high, but also rotate your hip out and then possibly extend the high foot from that rotated position. This is going to require developing dynamic flexibility / mobility in your glutes, hip flexors, and hamstrings.
This image illustrates a fairly advanced high-step: high step.
What stretches to do
The stretch that the OP mentions (laying on ground, pulling knee to chest) is a good start, but that only stretches the glutes, and not the other muscles. That limits the range of movement you're working to a single plane (and doesn't help with rotating the hip out, or extending the foot).
I've had good luck doing the following stretches:
- froggies
- chair stretches
- "ATG" squat - a deep bodyweight squat with an upright posture
The Nicros website has a good resource on the first two of those stretches: Nicros stretching.
I can't find a great link about "ATG Squats". I have one from T-Nation that is full of blather and posturing and light on tips, but better than nothing. Here.
Leg strength and high stepping
I've also found that basic strength in a squatting position is helpful to fully execute a high-step. When I started climbing, my legs were pretty weak, and when I'd place a high foot, I often wouldn't have the strength to rock onto it and stand up. Sometimes this felt like a flexibility problem (my hip won't "let me" transition to the foot), but (for me) was actually a strength problem (my body thought my high leg was too weak to bear the load of my full bodyweight). I started doing a combination of bodyweight squats and (light, by most people's standards) back squats, and as the weight I was squatting got closer to my bodyweight, my high-stepping became noticeably smoother. Your mileage may vary.