Having them have their college or university send you an official transcript is both easy to do, and pretty common, at least in the US, for students who have recently graduated. Nobody will be terribly surprised if you ask for it. An official transcript is at least a partial replacement for a good work reference for new graduates, whose only work experience may be outside of the field.
So don't feel bad about asking for an official transcript. It's pretty normal, and it's cheap and easy to do. (If they're lost, have them contact the registrar's office at their university.)
However, good references and proof of a college degree doesn't necessarily equate to being any good at what you're hiring them for. You can cherry pick your work references, and I've seen plenty of graduates who couldn't do what their degree is in. I'm not sure how (maybe group projects or cramming for tests and forgetting) but it does happen.
So you want to design your interview process in such a way that it requires demonstrable proof that they can do what you're hiring them for. If you're hiring programmers, make them program. If you're hiring artists, make them bring their portfolio, and if possible, do some art while they're there. If they're going to be in sales, make them demonstrate their sales skills.
And of course, if they can do this, then perhaps the official transcript isn't so critical anymore.
Just call the school. The registrar's office should be able to verify whether a degree was granted.
But unless you're hiring for something where deep information theory / computer science expertise is required, work history should matter more in any case. Do not request your engineers provide their college transcripts -- it will come across as lazy (background checks are an employer responsibility), paranoid, and clueless.