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. 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
If for whatever reason you do not want to use Steam you can use Lutris. Start by installing Lutris on your machine, there is no one way of doing this without issues so please refer here <hyperlink here with https://lutris.net/downloads >. After installing Lutris download either season from the Windows section.
Extract the game wherever you want and open Lutris
Click on second icon from left at top of the window “Manage Runners”. Scroll down to wine and select “Manage Versions” Lots of versions pop up, you can install whatever one you like, although ge3.6 is a great base for many games.
Now click on the + icon. A new windows should open with some options, pick “Add locally installed game” In the first window “Game Info” give the game a name (can be anything). Choose “Wine” as a runner from the pull down. In the second tab “Game options” locate Minecraft.exe (season 1) or Minecraft2.exe (season 2) (if you downloaded Minecraft story mode from Fitgirl Repacks go to step 5, this is irrelevant to you) in the third tab “Runner options” DO NOT CHANGE ANYTHING, in the fourth tab “System options” you can change where Lutris will save files (default is /home/Games)
You should be able to press the save button now, Minecraft story mode should now be in your Lutris library!
FITGIRL REPACKS: If you torrented MCSM you will need to extract it first. Choose the setup.exe file you torrented in place of Minecraft.exe/Minecraft2.exe and in the third tab “Runner options” DO NOT CHANGE ANYTHING, in the fourth tab “System options” you can change where Lutris will save files (default is /home/Games)
FITGIRL REPACKS: Minecraft story mode (or whatever you called it) will now be in your library, double click it to begin the installer (note: the installer may only see files inside /home/Games/<your game name here>/drive_c or the directory you chose during step 5!)
FITGIRL REPACKS: After the installer runs successfully go back to Lutris and right click Minecraft story mode (or whatever name you called it) and press configure, head to the second tab “Game options” and change the executable to Minecraft.exe/Minecraft2.exe (these should be in drive_c but you can move them without issues) and press “Save” at the top right of the window
FITGIRL REPACKS: Minecraft story mode is now installed!
Note: A guide for Lutris was going to be written, but I (Droid) am not using Linux at the moment and I would have a hard time making the guide for installing Direct3D. There will be a small update in the future with this guide.