Well, if you are applying to a law enforcement agency such as the NYPD or the FBI, any one of the government security agencies such as NSA or CIA, a government public safety agency such as FDNY or EMS, or positions where you could have access to money such as a large bank or a Wall Street firm, you'd better believe that they'll check. Not only that, but for some companies in some industries, these due diligence checks may be MANDATED by government regulation or by law. If a company states to you that it's going to run these checks, it's safest to take them at their word.
References are individuals who will vouch for you in terms of your competence, spirit, initiative, team work, etc. If you don't have any, do the best you can: bearded professors who used to ignore you, grad student proctors who used to yell at you, the cop who arrested you at a demonstration - as long as they are willing to say on the record something nice about you, that's fine. You'll obviously get more selective as you gain more professional experience :)