You’ve probably Googled this to death, as I also have, and got mostly dumb answers like to reboot your phone, enable unknown sources, or even as far as to reflash/factory-reset your phone.
Nope. Just go to Settings -> Apps, tap the Menu button, then tap “Show System”. Scroll down to “Package Installer”, tap it. Check the “Permissions” line – “No permissions granted”? Right. Tap that.
In that menu, you’ll find the golden setting. Storage permission denied? Right, that’s a problem. Slide that beautiful little switch “on”. Then, back out, go back to your APK, and try again.
Thank me in the comments. 🙂