Legitimately

Physical

The Complete Adventure Disc is the only version to get unless you’re collecting. Buy it off eBay or another trusted site of your choice. Season Pass has episodes 1-5 downloadable.

Digital

Codes could exist, but I've never seen any pop up online at all. You can only redownload the game via the PlayStation Store if you had owned it previously.

How to redownload games from the Playstation Store on PS3

Click to collapse/close

Open the Playstation Store under the network tab of the XMB
Scroll down the left hand-side menu until you find "Purchase History"
Select Minecraft: Story Mode from the menu and redownload
Profit (At 20fps)

Yarr!

Homebrew

Modding The Console

A good tutorial for adding custom firmware to your console can be found here. For later Slim users and Super Slim users, a guide for HEN can be found here. You can check if your console needs HEN or CFW by visiting this website on your system.
Note: If you have a PS3 Phat or a Slim with the serial number CECH-20XX or CECH-21XX your system is definitely moddable. If you have CECH 25XX, it's a mixed bag, you'll need to check the above site. Anything after that can only install HEN.

Downloading/Running the Game
Download PKGi here.

NoPaystation database files 1. https://pastebin.com/QQM81GfW 2. https://pastebin.com/ui8jJreC Click download and make sure you have 2 files called config.txt and dbformat.txt.

If you haven't already, install PKGi and Multiman on your PS3. Once you've done that, go back to your PC and copy the 2 files called config.txt and dbformat.txt onto your USB. Plug the USB into your PS3 and launch Multiman. Once in Multiman navigate all the way to the left and select
File Manager / mmOS.
Use your right stick to move the mouse and X to open/select files. Open the file called PS3 ROOT . A window should pop up with some files and folders. Open dev_usb it might have some numbers after it like 000, 001 or something similar that is fine just make sure when you open it you can see your config.txt and dbformat.txt files.
Now press X ONCE on config.txt and dbformat.txt then press o (circle) and press copy. Now close the window and click on PS3 ROOT again. Navigate to dev_hdd0 then game . This might be different for everyone but just open the folder that has PKGi in its name. Then open the folder called USRDIR . In here press o (circle) and press paste.
The hard part is done. Once you have pasted those 2 files in that folder successfully, you can now go ahead and quit Multiman. Once on the XMB MAKE SURE you are connected to the internet and launch PKGI. (It's near Internet Browser). Now when you launch PKGi it will throw an error, this is normal. There should be a menu to the right if not press △, go down and press Refresh . Now it will start downloading the latest database files from NoPlaystation, and when its done it will show you all the games. Now you can go ahead and download any game.
Once its finished downloading you need to install the game. To do, this quit PKGi and go to Package Manager then go to Playstation Network Content. Here you will see your game, just go ahead and install it and play! Some games require updates/download extra content by asking you to sign into PlayStation Network, this is fine and you can just sign in to download the updates/content then sign out.

Credits to u/shapedrogue6 on Reddit for the guide. Edited by Pixel.