5. A deadly non-linear world... except, not really
Non-linear worlds are inherently more difficult than strictly linear worlds because the player is less likely to know what they're supposed to be doing and is more likely to run into areas that they're unprepared for.
Dark Souls appears to be very non-linear at first glance, but in actuality it's a lot more linear than it seems. To start, individual areas tend to be very linear -- albeit with hidden treasures to be found in various side paths. But as far as the game's overall progression goes, Dark Souls has a heavy reliance on gating. The game opens up a portion of the game to the player and then to access the next set of areas, a certain task or series of tasks must be undertaken.
Excluding the tutorial area, there are basically three major goals that must be accomplished in order to reach the final boss. The first goal is to ring two bells (each of which is guarded by a boss). Starting in Firelink Shrine (the initial hub area), there are three areas the player can travel to -- The Catacombs, New Londo Ruins, and Undead Burg.
Powerful skeletons that come back to life soon after being killed guard The Catacombs, and New Londo Ruins is filled with ghosts that are invincible unless the player is cursed, or uses a certain item. In contrast, Undead Burg has enemies that are similar to the enemies in the tutorial area and is the obvious choice to start out with. Right from the start, Dark Souls is subtly funneling the character into the course of least resistance, and it continues to funnel the player through the entire two bells portion of the game, by giving the player keys that indicate where they should go next.
After the two bells have been rung, the second part of the game begins with a cutscene that shows the player that a huge fortress that was previously locked has now been opened. The player's course is clear -- explore the fortress and the area beyond it. This portion of the game is one of the most linear, with two areas that must be completed in succession and only one optional area. This section acts as an exam: If the player can completes these two areas (some of the hardest in the game so far), they're deemed worthy for the third main portion of the game, where the entire world (minus the final boss area) is opened up to them.
By gating the areas of the game in this manner, it allows Dark Souls to have a more measured difficulty curve than a truly non-linear game would allow. The areas opened up in the third part of the game tend to be more difficult than the areas in the second part of the game -- which, in turn, are more difficult than the areas in the first part of the game. This helps to prevent the player from getting truly confused and lost like they might if the entire world was accessible right from the beginning.
6. Provide hints to the player, but don't be too obvious about it
Probably my favorite example of how the game provides hints to the player is early on, at the beginning of the Undead Parish. The player runs into an armored boar enemy that proves to be much more powerful than anything the player has had to fight so far. A frontal assault is likely to prove ineffective, but there's a set of stairs to the side that the player can escape to.
After a few relatively easy fights up the stairs, the player discovers several monster lure items on a ledge directly above the armored boar. What the player should do soon becomes obvious -- throw a few monster lure items into a nearby fire, and watch as the armored boar commits suicide by running into the fire.
A lesser game would have had given the player a message like "Try throwing the monster lure at the fire to kill the armored boar!" when they picked up the monster lure items. By not explicitly telling the player what to do but by leading them towards the answer, Dark Souls allows the player to feel clever for figuring the solution out.
7. Combat is a replenishable resource
One of the smartest changes Dark Souls made over its predecessor was the switch to the bonfire system. The previous game, Demon's Souls, uses a traditional resource system where the player can restore their health and magic points (MP) with items that they can find and purchase. However, in Dark Souls, the player is given a set number of heal potions to use. Additional potions cannot be found; however, the player's potions are restored every time the player rests at a bonfire. Likewise, the player is given a set number of spells they can use each time they rest at a bonfire.
The replenishing resources bonfire system has a number of advantages over the way that Demon's Souls did things. It encourages the player to use all of their magic arsenal instead of just the spells with the greatest return-on-MP investment. It prevents the player from stockpiling huge quantities of health and MP items, thus rendering the resource system largely irrelevant. And it removes the need to grind out money and item drops when you're low on potions. Through the bonfire system, the player is encouraged to use all of the resources at their disposal, since they know they'll recover them next time they rest rather than having to worry about hording resources.