Let me see if I can explain what it means in the gaming world:
If you play, say, Call of Duty, you play mission A, then you play mission B, then you play mission C, and so forth, until you finish the game. You must play the game in that sequence. So you go:
start---a----b----c----e---end.
I.e., a line.
The Witcher, on the other hand, has different paths you can follow, or not follow, or follow half way. While the story takes you to roughly the same places from chapter to chapter, through the eyes of the same character, the decisions you make branch the story in different ways, and you end up doing different things, following different stories/paths. That is what they mean by non-linear. This would be very clear if you were to trace the different paths you can take from the start to the end.