You will always need to play Slug Village first - it blocks the way to any other levels, aside from the Bean-With-Bacon Megarocket which you can't really do much in at the moment. Once completed, almost all other Shadowlands levels are accessible, although not all of them are possible to beat at this stage. In order to unlock Fribbulus Xax, you will need to rescue two Gnosticenes - it doesn't matter which ones. You will also need to obtain the Pogo Stick, as the first level of Fribbulus Xax is impossible without it, and even rescuing two Gnosticenes without it is an extremely difficult task. You'll likely want to grab the Neural Stunner sooner rather than later too.
The Pogo Stick can be found in Lifewater Oasis.
The Neural Stunner can be found in Pyramid of the Moon. It is not possible to obtain the Neural Stunner without first having the Pogo Stick.
Gnosticenes can be found in almost every level in the Shadowlands. The one in Hillville is possible and realistic to rescue as soon as you've completed Slug Village. The one in Crystalus is also possible to rescue at this point, but extremely difficult - it's recommended you leave that one alone until you have the Pogo Stick and preferably the Stunner too. The ones in Sand Yego and Pyramid of the Sun cannot be rescued without the Pogo Stick, but can be rescued once the pogo is obtained. The remainder cannot be rescued at this point of the game.
When Keen respawns from a checkpoint, he retains all points items and progress / ability items he has obtained in the level up to that point. However, extra life and ammo pickups, and enemies, will respawn. In some cases, if you're short on lives and/or ammo after reaching a checkpoint, it might be easier to just restart from that checkpoint right away.
Just because you can't rely as heavily on shooting enemies doesn't mean there aren't other ways to deal with them. Aside from the classic weakness of Skypests, sometimes an enemy can be trapped in an area it can't get out of, so that it won't pose a threat. This is especially worth considering for enemies that like jumping, and could potentially jump into a pit they can't jump out of.
Like all good Keen games (and Keen 3), this game has secret levels - not just one, but two of them! The means of accessing one of them will be (at least in part) quite familiar to fans of the series, while the other is a bit more unique. If you don't manage to discover them on your own, the Shikadi might know something about them if you can find their notes. Be warned, the secret levels are extremely difficult!
Speaking of secrets - while secret areas hidden behind walls aren't as commonplace as in the official games, they do still exist! If you can't find them the traditional way, the minimap Keen can view using the Radar Chip will reveal the vast majority of - if maybe not quite all - secrets.
The following things are necessary for 100% completion:
Note that getting green flags, ie: completing levels with a perfect score and without restarting from a checkpoint, in a single run, is not a requirement for 100%. The two components of this - "complete without checkpoints" and "perfect score" - are requirements individually for 100% completion, but they can be done in seperate runs.
Additionally, by doing the above on secret levels too (where applicable), your completion % can go beyond 100%.