I think Brandon "the Builder" Stark is one of those mythical people who lived so long ago, no one is sure he ever existed. He also built Winterfell, as it happens.
The only explanation given on any of these things is that there are "spells" that are still active. Since Starks are not normally gifted with magic ("Three-eyed crow"-Bran being the exception), I think the implication is that he had help from the Children of the Forest. There are not many other who are overtly mentioned as having magic powers.
A connection between Stark and the Children of the Forest is implied in many ways, such as
the close relationship between Ned and Howland Reed (who in description sounds like the last remnant of "mainstream CotF" in Westeros), Ned worshipping the Old Gods, and of course (silly spoiler):
the Three-eyed crow keeping track of Bran's abilities.
I don't think we will learn much more about Bran the Builder and his works. I think it is mainly there as a mystery plot device, intended to send tinglings down the reader's spines when they read that Coldhands cannot pass the wall. Although it does beg the question: If Brandon could do such wondrous things with the Wall and Storm's End (what the heck was he doing down there building a castle anyway?), what might he not have done with Winterfell? Is The Ghost of Winterfell perhaps something more than just Toothless Theon?