Aragorn goes a'prowling where the stars are strange

[Dain]

I thought the stars were different in the southern hemisphere, though not completely. I mean, you are looking in a different direction...

As for when he wandered, I'd say there was plenty of time between '57 and '80 between (or even during) his survice to Rohan and Gondor when he could have visited far-flung lands. I'm not sure exactly when, though we do know he went south in '80, so maybe he was there scouting it out slightly before as well...