Unfortunately, Minecraft: Story Mode never released officially on Linux, meaning there is no native version and there's no way to get it legitimately. Although, it is quite easy to get the Windows version running on any Linux distro. If you're a Linux enthusiast, you'll probably already know what I'm talking about, but for all the Linux newbies, I'll provide a small tutorial.

Steam/Proton

Ensure you have Steam installed from the official website here. Once you do and are all signed in, click the "Steam" dropdown menu at the top, the click "Settings." Find the "Compatibility" section and click "Enable Steam Play for all other titles." Next, download the Windows version of the game here. Extract the files into a folder you like. Then back on Steam, go to your Library and click "Add a Game" towards the bottom, then click "Add a Non-Steam Game." Find the setup executable you downloaded and import it. It should show up as any old game in your Steam library. Then click play. The setup should launch like it normally would on Windows. If not, go to the game’s properties by clicking to cog icon, then “Properties.” Click “Compatibility” then check “Force the use of a specific Steam Play compatibility tool” and select your preferred version of Proton. Go through the installation and select a path that you like when installing. Once it's done, remove the game from Steam by clicking the cog next to the game, the clicking "Manage", then "Remove non-Steam game from your library." We do this because this game is still linked to the setup file, not the files it installed. After this, add another Non-Steam game and make it the .exe from the folder you chose to install the game to, it should be called something like "MinecraftStoryMode.exe." Launch the game by clicking play to ensure it works, and that should be it!

Lutris

First, download the game from your preferred Windows source. If you don’t already have it, install Lutris. Once you have Lutris open, click the + icon in the top left corner, then click “Install a Windows game from an executable.” Type “Minecraft: Story Mode” as the name (or whatever you like), then click “Install.” Next to Wine, click “Install” again. On the next page, change any settings you like, but it’s recommended to leave it as default. You can also choose if you’d like to create a desktop or app menu shortcut. Once you’re done, click “Continue.” On the next page, click “Browse” and choose the setup .exe file from where you extracted the Windows download, then click “Install.” Once it does it’s thing, it’ll open up the installer like any old Windows machine. Run through the installer like normal. Once it’s done you should be able to launch the game through Lutris!

Note: If you’re installing the GOG version, you’ll need to install the DLC episodes as well. To do this, in Lutris, simply select Minecraft: Story Mode, and on the bottom bar where it has the “Play” button, click the drop-down button next to the button that looks like a painting, and click “Run EXE inside Wine prefix,” and select the Adventure Pass installer from your extracted download folder. Run through the installer like normal, and all the episodes should be installed. You do NOT have to do this for Season Two.