In my opinion, I've always felt that a "linear" map is one where I've felt throughout that the mapper has led me every step of the way and I haven't had to do much thinking or searching for anything. There's only one way to go, it's obvious, and I go. Seems this usually applies to smaller starter maps.
I'd call a map "non-linear" if it has optional areas or routes, possibly secrets, where the extra ammo and power-ups are, but the exit could be found without visiting these areas. The optional areas and routes would make the map easier by the end but are not essential to reaching the end.
But these are just simplified black and white definitions, and as has been said above, there's a huge world of gray full of everything else we can imagine.