Okay, last time I mentioned the three different types of linearity (linear, semilinear, and nonlinear) in the Game Linearity article. This article deals with nonlinear games only, and how to make sure that when you say your game is nonlinear. it actually is. Thinking caps on? No? You don't need 'em anyway.
-What a Nonlinear Game is NOT-
A non linear game is not a game where you can freely run around the world and do stuff that doesn't progress the story whatsoever. It does not have objectives that need to be accomplished in a strict order, so that the player can have access to Area B. If your game forces the player to do things in a certain order, so that they can freely roam a bigger area, than you're game is semilinear.
-What a Good Nonlinear Game Has-
Freedom to do whatever they want in any order, and twist the story around, maybe change how future events turn out. Multiple endings is almost always necessary, unless all of your possible actions allowed are for a common cause. An example would be either killing the Empress or rallying the people against her to knock her out of the throne.
-How to "Control" a Nonlinear Game-
When I say control, I mean structuring the nonlinear part into the engine, instead of just writing own a buch of stuff that is possible and then scratching your head figuring out how to structure it. You could use checklists (I believe someone wrote this as a comment in the last article), or you could have flags that change certain areas or events when they are triggered.
That's all for now. I hope you keep this in mind when you make your game. A nonlinear game is a huge project, but these tips should save you some time.

Cha!