The basic question is - what are you doing?
We have a pretty good idea of the position of the nearby stars, especially the bright ones. (eg. Sirius)
We also have a good idea of the location of the center of the galaxy, something that would be visible from a lot of local space.
Plus, we know the location of a large number of globular clusters orbiting our galaxy center, not to mention local galaxies like Andromeda and the Magellanic clouds in our local group.
Presumably you could get a pretty good “triangulation” from any of those, taking into account the drift or angle change due to precession (everything moves).
First, understand the scale.
The nearest star system is Alpha/Proxima Centauri, 4.3ly away.
There are a few dozen known stars with pretty good measurements in the nearby 50ly or so.
If you travel within that 50ly, as Dracoi points out, you stop every so often and re-measure the parallax of at least the main stars (really bright ones like Sirius and Deneb) and more likely, every star you can find.
Eventually, as more and more people do this, we will have a map of stars and their relative locations.
The galaxy (Milky Way) is approximately 100,000ly across. Andromeda, about 1Mly away.
Unless you are proposing sublight voyages of tens of thousands of years, the movement of the individual stars is only a measurement adjustment not a problem.
Alpha Centauri will move from 4.3ly to 3.11 ly from Earth in about 27,000 years.
Presumably any computerized star catalog to navigate from will include adjustments for proper motion.
See this: Orion Arm - Wikipedia for our understanding of the general shape of our Galactic neighbourhood.
Add to this details like pulsar location relative to other stars, the galaxy center, etc. -
So the first intrepid explorers will not be heading out into the fog with no idea where they are headed or how to get back, or how to locate themselves.
We have a pretty good idea of the neighbourhood, and like most of science, we will build on that as we progress. It’s not like Magellan setting out on a voyage with only hazy idea of what was where…
(Unless they are Hollywood screenwriters. They seem to have no clue of the scale of planets and stars, they do stupid stuff like a moon blown out of orbit will pass a different star system every week… sort of like “I’m going to run out for a loaf of bread and some milk; oops, I’m lost, that looks like the Taj Mahal, and if I keep going for a minute, look, there’s the Eiffel Tower and I’ll catch a taxi to Big Ben and then hike over to Easter Island, and look, I walked home and the jug of milk is still cold…”)