I like the suggestions above, just giving you another option:
Whilst questing, rumors of new quests come with the navigation coords of that planet. Those coords are entered into the ship's navigation system, which then allows you to hyperspace to it.
BTW, if you only allow hyperspace jumps between planets, there is no need to have the entirety of space in game (ie: Infinity style). You'd be able to get away with each planetary system (ie: star plus any planets, satellite objects, etc) being an isolated scene, thus making it easier to manage.
I think this is a good idea. You divide the universe in zones where each zone has a coords coded with some integers. You can jump to each zone with the hyperdrive. Now you place planetary systems in certain zones and all other zones are just empty, maybe with some random stuff like asteroids (which could be generated procedurally from the zone coords). So everything is in principle accessible, but it is impossible to guess the few zones which actually have planetary systems. That is, you would have to find out the coordinates by interacting with other people etc.
You could still make things more accessible with better technology. E.g., you get the information that a certain planet is somewhere near (1000,4000,5000). Let's say 'near' defines a space of 1000 zones. Now you could visit each zone till you find the planet, or you could upgrade your scanning system which allows you to scan nearby zones for inhabitable planets or something, allowing you to find the planet in a much shorter time.
edit: another example for a single player open world rpg would be gothic 3