[I figured this was more of an element than a genre thing, since non-linearity can apply to pretty much any genre.]
The concept of non-linearity is a constantly developing idea within the world of video games. In the earliest games, you didn't need to worry about plot or any kind of progress, and you'd simply repeat the same bit of addictive gameplay over and over until you died and wrote A.S.S. in the high score table. Later, as games created all these varied stages to follow, you went along for the ride to see where it would take you. Arcade staples specifically, like the Beat-Em-Ups and the Rail Shooters, would just be one long road between the start point and whenever you ran out of quarters.
Games started experimenting with the idea of having different paths to take around this time. The earliest factor, and one that is still relevant today, would be the risk vs reward element, where you could choose whether or not to go for a bonus item for a higher score, despite the increased danger that going for that bonus would present. It is non-linearity in its most basest form: the first factor besides simple endurance that allowed a skilled gamer to rise above his inferior peers score-wise. This is what I call the "Bonus" or "Basic" model of non-linearity, where you purposely go off the easier, pedestrian track for a potentially higher score or a potentially earlier "game over".
The second is the also familiar "Branch" system, where you are offered choices and dilemmas which affect the rest of your playthrough. A classic early example would be the "go right? go left?" conundrum of the original Pitfall. Other, non-stage-based platformers (so excepting Donkey Kong, Manic Miner and Lode-Runner et al) would also frequently have alternate paths to take. The Mega Man series is famous for presenting all eight of its early stages simultaneously, and asking the player which stage/robot master he wishes to take on first. There's usually a "correct" path, which would lead to you getting the weapon from one robot master that is strong against the next one in the sequence, but most players had to figure it out on their own or would otherwise experiment with their own sequences. The Branch system is by far the most prevalent form of non-linearity, though how much it can deviate from the norm will often depend on the game: having to choose between doing two levels and then doing having the level you didn't choose right after, for instance, isn't deviating a whole lot.
The final system that is used with frequency and certainly more often in recent games, is the "Freeform" or "Sandbox" form of non-linearity, which started with the Roguelikes and continues with the ubiquitious MMORPGs of this era. In these games, you can pretty much do anything you want, or at least anything you want from a list of options that are available to you. If we're talking one-player games like GTA or Oblivion, there's usually a string of story-vital missions and quests that you must follow (eventually) to bring the game's main story to a close. Otherwise, you're free to explore the world and its many side- and sub-quests. A lot of 3D platformers are the same too, with collection subquests taking you all over the place, often extending the game's longevity in an entirely optional extent.
A concept that hasn't been explored much, or has so far only enjoyed minor success, is time non-linearity. So far in RPGs and the like, you can have a hero at level 1, follow any career path you choose, explore dungeons and missions in a random order until the hero reaches level 100 and is some kind of unbeatable super person. The many branches and paths create a strong sense of freedom, but the otherwise linear progression of time is still an ever-present ball and chain. Common narrative devices for dealing with a non-linear timeline, such as flashbacks or starting a game in media res, are accounted for, but true non-linear time hasn't really been dealt with much in the video game world. I guess for good reason too, since no-one wants to see their character suddenly become 5 years younger and 10 levels suckier. The few examples I can think of include the SaGa series, which were generally confusing as hell, and the frequent mental trips into the past with Lara Croft's younger self, when she had far less experience and acrobatic/martial ability and so you had to rely on nothing but youthful enthusiasm to escape danger.
I should probably end this article with some novel idea in the realm of non-linear gameplay. A concept that I'm tinkering around with is having episodes of a game played through in a random order, just to create a kind of jigsaw puzzle that comes together the more you play. If you have the one hero, or better yet some non-combative underling/overling that links all the episode threads together, and follow a group of heroes taking out a bandit fortress or ice dungeon or what have you in each episode. As well as receiving treasure - which you won't keep between chapters, and will probably end up going into an overall pot or some kind of "episode score" at the end of that episode - you'll also receive clues and items that will come in useful for some other episode. For instance, you may receive a Ruby Key in a crypt which actually opens a door in the volcano dungeon a few episodes ago (or a few episodes down the road). You may also see part of a combination in an abandoned mine which opens a safe in the bandit fortress.
This game would have around 50 (or maybe 49, since that works as a 7x7 grid) such episodes/dungeons, with the cast lists of each varying depending on who survived a previous episode. If you have an axe-wielding dwarf at level 10 for one such random episode and keep him alive, he may come back in a different episode at level 30. If you help one lovestruck hero find a piece of treasure to win over his potential sweetheart, she may appear alongside him as an additional hero in a later episode. Likewise, interesting things start happening if you go back in time. A hero that dies in one episode at level 40 by falling into some lava might mention during another episode (where he's younger and still alive) how much he dislikes extreme heat. Okay, that one's a little silly, but you might be able to do things that shouldn't have happened according to the timeline you're establishing, causing a red mark to appear on an episode you've already completed but somehow messed up by killing a character earlier on that was still alive when you originally did that episode. The repercussions of which I'm not too sure about yet: it may dock you on your overall score, if I decide this game has one, or it could simply allow you the choice of repeating the episode with all this new information in hand.
There are other things too, that may alter the future of some of the episodes. If you're particularly antagonistic or fail to adhere to the whims of a certain hero, he may not come back in future episodes. Inversely, treating a hero with a lot of care and attention may make him return in future episodes in which he wouldn't have otherwise appeared. If you have a favorite character, or one that you despise, you may want to keep an eye out for ways to make them want to come back or stay away. If you attempted a high-level episode but only had a bunch of weak characters and got wiped out, that high-level episode might look a bit different later on if you've befriended a bunch of power-gamer type characters in the meantime. The game really does offer all kinds of choices and decisions, plus a cast list that never stays static. You might want to aim for a hero to show up in almost every episode (which some kind of bonus for creating a regular character). Alternatively, you might keep killing heroes off to make new ones appear. There could be a collectible sidequest (there I go again) for the cast list, keeping in mind all the triggers that will cause them to eventually appear, such as finding an egg and keeping it so it'll hatch into a friendly monster player-character a few game years later.
Well, that's kind of a wild(ish) idea for a new(ish) type of non-linearity. Episodic non-linearity, I guess. If we could convince developers to stop trying to equate a gaming experience to sitting through a movie, we'd hopefully see more games that are open to weird and varied non-linear storylines just like it (I'm thinking the high sales figures of GTA and Oblivion should help).
