Literature search, to me, is like the recipe of potato salad: everyone has at least one, and they always claim that theirs is the best. In fact, we just use what we feel comfortable and, so far, has not caused any major meltdown. So, bear in mind that these are just what work for me, and you should modify them along the way.
Schedule a meeting with a librarian, now
Talk to a librarian at your institute. In our school we have a medical librarian and perhaps you may find one specialized in your field as well. They are trained to locate useful information and are up to date with related technology. Give them a clear field of study and even a gist of your research, and ask for a good list of databases. I may go so far to say that a good database list is half of the game. Apart from the list, learn Boolean and learn them well, pick up a good electronic reference manager software. Your library should have these resources.
Also, ask your library if they have any library consortium. Some major institutes have large amount of subscriptions which open the gateway to many full articles. If your institute is tight on budget, a lot of the time you can just find abstracts sans full text. Having a consortium library card may grant you access to other bigger institutes' library, in which you can print or photocopy their articles. On the same note, ask for an introduction on doing inter-library loan and how much you're supposed to pay.
Learn systematic review
Systematic review, simply put, is performing literature review as a scientific research. It's problem-based, protocol-focused, and the process is meticulously documented and hence readily replicable. There are plenty of publications about this skill. I have been using Booth's Systematic Approaches to a Successful Literature Review and so far it serves me well.
Focus on the chapters about question formulation and ways of collecting data. I think even we are not heading for a formal systematic review, learning how to keep a clear search records, draft a conceptual framework, and maintain a paper trail would still be very beneficial.
Understand the cataloging system
In biomedical field (where I work) we have MeSH (Medical Subject Headings) which shows the hierarchy and grouping of keywords. Consult the librarian and see if such thing exists in your field.
Read a few systematic reviews or literature reviews in your own field
To get the general picture, I actually first start from Wikipedia and encyclopedia. If you already have some background knowledge, you can probably skip the first phase. After meeting with the librarian, use the new-learned technique to find a few literature reviews or systematic reviews (hereafter "review") in your field. Review articles provide general scopes and a rich pool of keywords for your later use. You can also perform a reference tracing technique on these articles because they usually have unreasonably nice and comprehensive bibliography.
Spend some time with the online search engine and really read the "read me first" and "how to use this site" links. Learn how to massively download cited articles from a hosted article and export them to your manager software of choice.
Another good reason to start with these articles is that they are all required to report the information retrieval in details. Which engines were used, how articles were screened, what were the criteria, etc. You can get a good sense of how researchers do it (or appear to want to be seen doing in order to look trustworthy.)
Start casual
Through this snowballing technique, a small body of articles should start to form. Pay attention to their use of words, keywords, etc. It's still somewhat a toying phase but you should start using your tools seriously. The only recommendation from me is at least one electronic storage/manager software should be used. Make sure you can integrate this software into the word processing software in a harmonious manner, and be able to export a formatted document on the fly. For the rest, it's personal choice: index cards, Post-it notes on the wall, writing on a poster size paper, etc.
Now, many fun tools are available... mind map allows you to cluster the ideas and words, citation map allows you to trace the ancestors (cited) and offspring (citing) articles of any indexed articles, word cloud allows you to identify the most frequently used words, some of these functions are also embedded in manager software such as Qiqqa, which is largely free and powerful.
Then get serious
After a week or so, you should have a good command of the tools, the software, the databases, and the keywords. Now you just need a question. Personally, all literature review should be problem-based. If someone asked you to "go and understand the field," that is just simply absurd. It's like searching an encyclopedia without anything to search; while there may be people who enjoy randomly reading wikipedia entries (I do, to confess), but that's not the best use of PhD time. Isolate the questions from your study before doing any literature search.
Now, what to search? I work in biomedical field so your and my paradigms may differ. For me, I usually go by this sequence as a starter:
Definitions: How does my field define XYZ? What are the controversy of the definitions?
Operationalization: How does my field capture/measure different contexts? How do we approximate "poverty"? How do we call a good "user experience"? etc.
Data source/Research design: What does my field do when they study the phenomenon of XYZ?
Analysis: What is some specific analysis for a certain type of design?
In a way, use the first literature review to solidify and fortify the understanding of every single phrase in your research questions and specific aims. Then expand to other questions (you WILL have branching questions along the way, trust me. It'd be hard to suppress them). Stop when you feel you have somehow exhausted the answers, and/or you're happy with the results.
Never start a literature review without a question, or you'll find yourself still only reading paper 18 months into the PhD, and that is probably not good.
PhD is not a between-people competition
You mentioned that sometime you saw others finding stuff that you did not. I'd suggest just ask them how they did it. Just because you asked them doesn't mean you're worse than they are. If they found something you didn't, get the references, read them and incorporate them into your manager, and instantly you're as well informed, if not better informed.
Talk to experts
Find some prolific faculty members and researchers, and ask them for tips. Collectively you should be able to get something more out of just talking to the librarian. Experienced researchers also tend to know more about the seminal work. And if you can get that list, compounded with the ability to trace the work's offspring, you can pretty much recreate the family tree of a particular key research theme.
Use crowd-sourcing
Websites like Mendeley and Research Gate utilize social bookmark approach and you can refer to other people's collections of articles/citations. If you have a good peer in your team, you may also divvy up the work and then evaluate the findings together, exchanging references, etc. Also some young researchers may be on other social sites such as Reddit (but refrain from checking funny videos) or crowd sourcing sites such as GitHub... you may consider setting up an account and set up a chat thread or a project for others to contribute.
Exploit all services of journals
There are at least a few services that you should see if your field's prime journals provide:
1. Mail alert: Some journals or search engines will send you e-mail when an article containing any of your preset keywords is available. Get like a weekly notice from them, and you can keep yourself somewhat up to date.
2. Twitter: Same as above, but through Twitter.
3. Digest: Some journals may boil down their published works into short pieces then feature them in the form of an online billboard. Occasionally a third party may do that as well for a nominal fee. For example, MDLinx summarizes key medical journal findings and e-mail them to subscribers as a 5-minute digest every day.
Pay attention to "grey literature"
Notice that in some fields there is a tendency to favor publishing results that are statistically significant. Relying solely on literature database is only unbiased in the domain of the published literature. Sometimes, grey literature such as conference abstracts, documentaries, unpublished papers, white papers, proof-of-concepts, blog posts, grant proposal archives, trial registries, patents, personal communications, and general mass media may needed to be explored as well. Each field has their own literature graveyard and atypical channels of documentation, you'll need to talk to some specialists in your field.
Be always on
To me, literature search is really more of a lifestyle change rather than an activity. Now I have camera to take snapshots of posters, take verbal and written notes. I bring index cards for writing. Etc. When talking to people I often drive the topic to what cool papers they recently found. That's my best way to deal with potentially tricky water cooler conversation; either I'll learn something or they'll leave me alone.
