Awesome question! I was just commenting on evidence in a post focusing on conspiracy theory.
As others have suggested, different philosophers have different ideas about what constitutes "evidence," "truth," etc. I up voted Guill's answer because it emphasizes the fact that there are different amounts/types of evidence.
However, he listed some amounts, but not types, so I'd like to elaborate on the latter.
There's direct evidence, which may include "smoking gun evidence" (best of all, a signed confession).
There's circumstantial evidence -- evidence that tends to prove a fact by proving other events or circumstances which afford a basis for a reasonable inference of the occurrence of the fact at issue
In politics and conspiracy science, we may focus on historical patterns and connecting the dots.
For example, if you know that conquest, intimidation, conspiracy and exploitation were attributes of the Greek empire, the Roman empire, the Spanish empire and so forth, you might suspect that these are attributes of ALL empires, including the current U.S. government.
And if you know that Bill Gates' wife and pal (Warren Buffet) both sat on the Washington Post's board of directors, you might "connect the dots" (a form of inference) and suspect that Gates is using his power to influence the media.
Another type of inference is used in studying evolution. Having already established the fact that organisms evolve, scientists can assume that modern whales must have evolved from some other organism. And if they haven't yet found fossils of whales' direct ancestor, they commonly refer to it as a gap in the fossil record (or "missing link").
Yet another form of evidence is reality. If the media tell you the government's doing a great job, the economy's improving, blah, blah, blah, but your salary is stagnant, your benefits are doing downhill, and you see more homeless people on the streets every week, you might be a little suspicious.
Then there's "God." Some people say everything we see is evidence of his (or her) existence, while others say there is no evidence for God whatsoever.
In summary, instead of asking WHAT determines lack of evidence, we might ask WHO determines lack of evidence. There's a lot of cherry-picking involved. Consider judges' often mind boggling ability to dictate what's admissible as evidence and what isn't.
Your second question is more complex. What do you mean by "no evidence" - no DIRECT evidence, or no evidence altogether?
And what do you mean by "believe"? Are you talking about a rock solid belief, or do you include suspicions or theories?
With a background in science, I'm personally inclined to not believe in anything for which there is no evidence. However, that evidence can be indirect or even theoretical.
If I'm not mistaken, Carl Sagan believed in the existence of intelligent species on distant worlds, though there's still no real evidence of their existence. On the other hand, we might argue that Earth itself is evidence. If life can evolve on a planet in our solar system, why can't it evolve on planets throughout the universe?
What's really interesting is Sagan's rationale explaining his theory that "space aliens" have never visited Earth. How do you explain the actions of beings that may not even exist? Yet Sagan used some elegantly simple logic to form an explanation that further tells us that UFO's are not associated with space aliens.
P.S. Another thing I forgot to mention is familiarity with evidence. I recently read a story about Stephen Gould (of evolutionary science fame) visiting a dig in Kenya (Olduvai, I think). The Leakey family was renowned for their ability to spot the fossilized jaw of a mouse at a distance, something Gould couldn't do. Yet Gould, who did a lot of work with snails, was the first to spot a fossil snail at the site.
So when someone says "That isn't evidence," it's possible they can't recognize the evidence because they don't have the proper training or experience, or they could be a propagandist who denies the evidence that's in plain view.