Guess about the paper's relevance by the frequency of its citation. This can be done by looking at http://citeseer.org, or observing the bibliographies of other important papers informally. If the paper isn't very relevant, you'd be better off spending your time on one that is.
Check the title, where and when it was published, and who its authors are. Papers by key people and in key conferences and journals give the paper a higher priority. Recent work should take precedence over older, outdated work. (Although sometimes it's important to know seminal papers from the past in your subfield.)
Read the abstract and the first page. Does their problem approach make sense and address the issue you're interested in? Don't waste your time reading a paper in detail if it lacks applicability to your problem and approach.
Read the section headings. What direction do they go with their approach, and what are their main contributions?
Look at the pictures. What do various diagrams and plots actually show?
Skim the paper. Look for the main conclusions and contributions. Avoid spending time on proofs, detailed derivations, etc.
