The conjunctive particles ど and ども are Classical Japanese contradictory conjunctions, like the English but and although. Although they aren't used as much anymore, you surely know them from the modern けれど(も), and you probably know them from いえども and されど as well.
They attached to the 已然形 (realis stem), which in modern Japanese has been reanalyzed as the 仮定形 (hypothetical stem). In this case, that stem is 歩け, so you get 歩けど.
Here, the 〜ど〜ど pattern has the verb redoubled for emphasis:
Since it's literary, we could try to give it a literary sounding translation:
Walk and walk as I might, I could see only rocks.
Hopefully you can see the meaning from this simplified example.