“Sure we should go in?” I asked Mary as we walked along the wall of a high school.
Obviously, they aren't walking on top of the wall. What's the correct way to describe that they were walking beside the wall?
The comments are illuminating, but the question deserves an answer, I think.
"Along" clearly conveys the relationship between the walkers and the wall, as do both "alongside" and "beside."
Because prepositional phrases are often idiomatic, there are few rules beyond common sense and logic to guide a writer to the "correct" preposition. The community of traditional users of English has determined over time which usages are "preferred." The researcher is thus left with lists of idioms.
Wood (1967) offers a potentially useful reference, English Prepositional Idioms. A more immediately accessible (if lengthy) resource can be found at http://www.advanced-english-grammar.com/list-of-prepositional-phrases.html
The phrase that would differ least from what you wrote would be "walked along by the wall".