Normally, since Fly and Surf are pretty good in battle, my Charizard and Kyogre have Fly and Surf, respectively. So if I am going to stay in a specific area, like the Battleground, I take the Pokemon I am going to train with me, and pack the HM Slaves away in the PC. If I am going to go into the field and train, I just take Bibarel, because it has Rock Slide, Strength, and Rock Smash, just what I need in a cave.
I also use Staravia (In Pearl) and Skarmory (In Platinum) for Flying.