It was definitely difficult, more than interacting with somebody of a different language and culture today since the natives were vastly different due to their and the Europeans' isolation from each other. I guess they at first relied on ideas that were common to most every human, like "if I don't attack you, I might not be hostile". Then, perhaps they used pantomiming or something to learn words of each other's languages. Then there would be people who knew bits of both languages, and could translate for others. Many native tribes had experience learning languages while trading with different tribes, so it may not have been as impossible of a task as you think.
