I think the game definitely does not have the "best story", but I think it delivers a very good example of storytelling that doesn´t rely on exposition and is woven into exploration instead.
Some games facilitate interactive storytelling primarily via dialogue choices, this one does it via exploration and encouraging use of imagination.
It gives players an opportunity to become virtual archeologists who collect fragments of evidence provided via level and art design, small bits of NPC talks or item descriptions and through these possibly gain more insight into the setting and their purpose in the gameworld.
There is a story of what transpired before players enter the scene and there is a story surrounding players themselves, but there isn´t quite enough of the above mentioned fragments for these to be conclusive, they´re ambiguous (back)stories, as far as the complete picture goes.
There´s enough evidence for smaller parts to be reasonably conclusive though. For the other parts, those who feel like employing their imagination can try to fill in the blanks themselves and there´s usually at least some evidence to anchor these blanks somewhere.
Story-wise it´s a stranger in a strange land game where the land doesn´t really care player is a stranger, except for taking advantage of it when it comes to the core plot.
Even if I´d concede there´s isn´t "a story", at least not in a traditional sense, the game still presents players with events constituting its lore as well as happenings "in the now" and I´d say it does a good job utilizing storytelling techniques unique to the medium to convey these. The nebulous story aspects also go well hand-in-hand with the game´s intended oppressive general atmosphere.
The game is also not a primarily story driven one and most of the above is pretty much an optional bonus. It´s certainly not a game for those who need a strong story drive to engage in (continuing) playing, but for the others there´s still a fantastic combat, well crafted atmosphere elements, level design and exploration with rewards besides lore/story bits. And, as usual, there´s always a place for an emergent story stemming from just progressing through the game and I´d say Dark Souls provides a good ground for this to be possibly a memorable one, particularly on a first playthrough, thanks to its non-linearity, varied encounter design, difficulty balance or online aspects.
If the game was supposed to be a primarily story driven experience I´d say its storytelling is definitely inadequate, but as an additional means to immerse players in the setting and possibly inspire some detective work I think it´s pretty damn alright.
Personally I don´t even really care whether the complete "story" in creators´ heads is good or not, or whether this approach stemmed more from budgetary rather than artistic reasons, I only know I enjoyed the digging and engaging with the game´s story elements on the side was fun and refreshing.
I disagree with the title of the article (haven´t read the article itself), partially because, as implied above, I don´t think this type of storytelling with Dark Souls´ level of obtuseness would work well in games where story is a primary focus, and partially because I don´t believe there´s any approach to storytelling inherently best for computer games in the first place.
I also don´t find Dark Souls´ execution to be flawless - I don´t like that some of the more important facets can only be discovered pretty much by accident and I think there´s a bit too much blanks for its own good (whereas Dark Souls 2 comes with somewhat fewer blanks, but some of those present are big enough to prevent any reasonable inference whatsoever).
Overall, in my book Dark Souls´ storytelling was adequate, well fitting with the whole and refreshingly creative (though not necessarily unique) and I´m glad this kind of approach has its place in the gaming landscape.
There are other ways to take advantage of unique possibilities of the medium when it comes to storytelling and I don´t think there´s much need to put some above the others. How well these work in concert with other design aspects is what I consider of importance and worthier material for comparisons.