What does it mean for a game to be linear?

A linear game follows a strict path for the player with little, if any, deviation. Basically, you traverse from stage 1 to stage 2 all the way to the final stage. Take, for example, Ghosts and Goblins or Magical Pop'n.

A non-linear game deviates in some fashion, either throughout the whole game or just for a portion. For example, the classic Megaman series was one of the first non-linear types. You had your choice of 6-8 stages at the start, but once you completed those you were on a linear sequence. Then you have a game like Metroid, where you just have one very huge stage that requires certain upgrades to reach certain areas but you can approach it from nearly any angle.

A freedom of choice on what you want to do in order to progress the game in order towards completion, that is what non-linearity is. So by extension, linearity is when the progression of events which actually contribute to game completion are sequential. In most cases, there's also no form of going backwards.

Usually, when people talk about "linear games" as opposed to elements like "linear gameplay" or "linear story", it's talking about the layout of the levels in the game. Not the structure of those levels, but the overall map of objectives that you go through. Games can have very open levels and maps, yet still be a "linear game" due to the approach for actual game completion.

An example of linear level layout is Iji, which might surprise anyone who has played the game that I've stated it. In terms of story and gameplay, it is extremely variable and non-linear. Each individual level is vast with many approaches possible depending not only on your actions in that level but also actions in earlier levels. But the level layout is a strict, one-directional set of levels accessed by completing the previous level. It's also a perfect example of why linear design is not necessarily a bad thing.

An example of non-linear level layout is Super Bomberman 5. Each stage has the same objective of "defeat all enemies", but clearing it opens gates that point to stages. Like a Choose-Your-Own-Adventure book, each new stage presents a new choice, and some branches will intersect at various levels. Each world has around 3 separate boss levels which you only ever get to one, and there are even different variations on the final encounter. Once you've cleared the game, you can then opt to start at any level you've cleared before, in order to explore the other gates. So even though the story and gameplay are rather linear, the level layout is pretty much the epitome of non-linear.

"Linear" can be used to describe the story of a game, or how the levels are played, or both.

I would describe it like this:

Linear maps/levels means that the player doesn't really choose how to tackle a level, they are corralled through it given little or no choice which path to take or how to solve a problem (or kill something). You may backtrack or take side paths but if there is one way through the level it can be considered linear.

Linear stories are ones that the players actions do not affect how the story is played-out. The opposite is a game where the player's actions (either in-game or between levels) can change the course of the story. I would include games like GTA and Borderlands where you get to choose which parts of the story you pursue and when.

Generally if a game's levels are completely linear then the story normally is too (there are some exceptions where games let you make story choices between levels). And if the levels are very non-linear then the story is as well. Most games fall in the middle of those extremes though.

Extreme examples:

Linear: rail shooters (like House of the Dead).

Non-linear: sandbox games (like GTA).

Most games are somewhere in between these two extremes. For example, in PoP:SoT you can go anywhere, and it has a very open feel, but brilliant level design works as a very subtle guide, and you end up on the one path through the game, rarely getting "stuck".

I think it usually means that the player doesn't get any choice in the way the story / gameplay evolves.

A game in which you progress from area 1 to area 2 and so on - without a choice to maybe take a shortcut from 2 to 4 and then (maybe) go back to 3 - is called linear. The direct opposite of a linear game is called as sandbox game - where, like a sandbox, you get to do whatever you want, there's less emphasis on a specific sequence of events that must be taken.

There are many levels of linearity between a completely linear game and a sandbox game, though.