It is, but there are simple ways around it:
- It helps if you can identify small, local "clusters" of stars. E.g. even in a very dark sky where you can see stars you never remember seeing, Orion's belt is very easy to recognize, because three collinear stars so close together are a fairly rare sight. Same for the North Star -- it's not too bright, but it's related to two very recognizable constellations and you can find the North based on other clues as well, so you know where to look. Once you've identified one constellation, it's pretty easy to find the other ones.
- It also helps if you're familiar with how the sky looks in various seasons. This way, you have a pretty good idea about what should be where. Granted, this probably doesn't work well if you have to travel a lot. My home country is pretty small; in its northernmost point, the sky looks pretty much the same as in its southernmost. If I suddenly found myself transported from Maine to Texas, I imagine I'd be in some difficulty.