Initially, the Balrog held onto Gandalf to keep the latter from escaping. However, as the wizard got the upper hand, the monster fled, up a single long stair. Then Gandalf managed to keep them together, either by holding onto the Balrog's heel or (if he was speaking metaphorically) by following closely after it, as it climbed and climbed:
From The Two Towers, book III chapter 5 ("The White Rider"):
'We fought far under the living earth, where time is not counted. Ever he clutched me, and ever I hewed him, till at last he fled into dark tunnels. They were not made by Durin's folk, Gimli son of Glóin. Far, far below the deepest delving of the Dwarves, the world is gnawed by nameless things. Even Sauron knows them not. They are older than he. Now I have walked there, but I will bring no report to darken the light of day. In that despair my enemy was my only hope, and I pursued him, clutching at his heel. Thus he brought me back at last to the secret ways of Khazad-dûm: too well he knew them all. Ever up now we went, until we came to the Endless Stair.'
'Long has that been lost,' said Gimli. 'Many have said that it was never made save in legend, but others say that it was destroyed.'
'It was made, and it had not been destroyed,' said Gandalf. 'From the lowest dungeon to the highest peak it climbed, ascending in unbroken spiral in many thousand steps, until it issued at last in Durin's Tower carved in the living rock of Zirak-zigil, the pinnacle of the Silvertine.