First off your going to have to find the map mod you want to use, should be easy enough seeing as you probably already have one since your looking at this guide. For the purpose of explanation I will be using the "Multi Galaxy V2 Map Pack (1000 - 10000)" created by skud13.

The next part is probably the most difficult (which just goes to show how easy this whole thing is), you have to go into the stellaris properties tab by right clicking on it, on the left in your library and go to the beta tab, this is where the gods themselves, Paradox Interactive, have blessed us with the power of time travel.
You will have check which version of the map you want was last updated too, the the map I'm using it says version 1.3 so I would select 1.3.2. After that just let the game sort itself out with the download which, depending on when you are reading this, should be about 200MB.

When you finish that download boot up the game. The DLC tab doesnt seem to affect the state of the game even though some of them weren't out then (that's probably why), so go right to the mods tab and turn off every mod except the map itself.
Personally I do this before I set my game back to the Heinlein version but I really don't think it actually makes a difference.
Now just let the game start up.

When the game is opened up you're going to need to create your race, this will have one of two results, nostalgia, or disgust, depending on how you found the old system. It really doesnt matter how you make it, just know that, as far as I know, you can't play as a hive mind using this method (sorry fellow swarms).

PLEASE NOTE: When you make this race it is HIGHLY recommended NOT to choose hyperlanes. This is beacuse of how we update the map, and how hyperlanes worked seemed to have been changed somewhere along the line. If you do choose hyperlanes then be prepared to be stuck in a single system until a fanatic purifier comes along. This also means that you should set the games settings to either "Warp only" or Wormhole only" in order to actually have a challenge, or not, it's a free country.

Now, with your empire created just make the game and when it has loaded up, save. Don't do anything else simply for the sake of actually playing in the updated version, it shouldn't make too much difference if you do decide to do things, but try not to. You should also probably make sure that it's cloud saved, just in case.

Now what you have to do is, after saving this game, close it and, like before, go to the beta tab and switch it back to opting out of any betas. This will restore your game back you the current version which, at the time of writing, is about 700MB. Sort that out, open the game and run it again, still using only that map mod which should be out of date now. If the game loads to the main menu successfully then you should be ok. Load up your game, queue stuff, let it run a couple days then save again. You should now be ok to close and install other mods but make sure the map mod is there.

That's just about everything then, just remember that hyperlanes are most likely a no-go and also bewarned that when you update you are going to be stuck with the old system government until 20 years in. You are likely to start off with no food and everyone in your empire will have base 0% happiness for the first month or two, which also means a scary unrest alert. Basically just some minor stuff that you don't really have to worry about but still, just a heads up, literally just move one or two people around to make more food but also just don't worry about the unrest, it will fix really quick. Also, don't choose what back then was known as "Collectivist" and "Individualist" as they were not updated but changed, unless you want to roleplay as a fallen empire.

Anything you want to add or any other issues let me know.
Images coming at some point