First comes research, of course. If it's an undocumented language, you learn about the languages that are potentially related or nearby it, as well as the culture of the people who speak it.
So often the real issues of documenting a previously undocumented language are social or political, so in all likelihood there are many battles to fight before you'd ever actually study the language itself. A professor of mine had to meet with the tribal council of a Menominee res many times as they repeatedly changed their mind back and forth over whether she was welcome. And this was documenting a language the speakers of which literally only number in the double digits.
Once you're in good graces, learn the phrases for "more slowly please" or "please repeat that." If you're really starting with nothing in common, I'd imagine you'd have to start with objects you can point to. Here's a great word list to start with. (Also, here's a lovely article on interacting with others when there's no language shared.)
When you have the basics of the language down, being prepared for your time with your subjects is very important. It helps you collect data you can actually use. Wanna know how the language handles plurals? Hold up one leaf, then hold up two. Hold up one rock, then hold up two.
Although I hope there are completely undocumented languages out there for us to discover, I think most commonly field linguists these days are trying to document endangered and moribund languages, and that's an easier process because there is probably a younger generation that is bilingual who can interpret.
There are all sorts of practical considerations too: obtaining permission from speakers to record them, what kind of technology you need to record them and analyze the data, etc. Also, invest in some Moleskine notebooks.
When it comes to the language itself, I highly recommend Describing Morphosyntax: A Guide for Field Linguists. It really is a handbook for the first time field linguist and walks through every item one should consider when documenting a language: the language's genetic affliations, sociolinguistic concerns, morphological typology, defining the grammatical categories of the language, constituent order typology, pragmatics of the language, etc.
(Also, it's a must for anyone making their own conlang.)