The process for building bases has changed in the NEXT update.
Starting a new base
Just find a spot you like the look of and build a Base Computer. It's in the quick build menu, z on PC, I believe is d-pad down on a controller.
Build your case computer, and interact with it. This will kick off the process, where the game will allow you to claim the area. After this your build menu will include all your base items and you're ready to start construction.
Recalling an existing base
You will need to obtain Navigation Data items, either from finding them in Outposts and containers, or buying them from the Galactic Trade Network. Buy quite a few, about 30.
Go to your chosen planet and build a Signal Booster from your quick build menu. Place this and interact with it. Select the option to use 1 Navigation Data, and proceed to scan the planet for 'Habitable outposts'. Hopefully you'll see 'Shelter found' and it will be marked as 'Habitable base'.
You are looking for a Habitable Base to show up. Just keep trying until you find one. If you feel unlucky, pickup your Signal Booster, and fly to another area.
Once you've identified the spot, fly over there, and you should see a huge flat open area, just like in the Foundation update. There should be a Base Computer in the middle of the area.
Interact with this base computer and you'll be able to restore your base.
Video for reference
It seems that existing bases are re-loaded 'as-is' meaning all your storage is restored as well.
The process is detailed in this Reddit post.