I can't think of the exact name for it, but anyone who has spent several days at sea in a relatively small boat and then gone onto land knows the feeling... Where you still feel like you're on a rocking boat. I think it happens because at sea you're body is constantly trying to compensate for the rocking, you get off, then the rocking is gone but your body is still anticipating it.
So how after months at sea did they deal with what must have been really terrible dizziness / vertigo because of this phenomenon?
You're talking about the phenomenon known as "getting your sea legs" or conversely "land legs." The vertigo wears off fairly quickly, especially once you switch from sea to land quite often.
One thing to keep in mind, also, is that voyages of exploration would stop at ports or at least land boats at streams or towns fairly often to replenish water and stores, so it's not like they were literally at sea for years on end.
Jschooltiger is correct. I worked on boats and ships for several years and can confirm. "Sea Legs" went away relatively quickly for me, what was difficult was adjusting to sleeping in a bed that wasn't rocking you to sleep.