After some research, I think the best answer is Xerces, as it implements all of XSD, is cross-platform and widely used. I've created a small Java project on github to validate from the command line using the default JRE parser, which is normally Xerces. This can be used on Windows/Mac/Linux.

There is also a C++ version of Xerces available if you'd rather use that. The StdInParse utility can be used to call it from the command line. Also, a commenter below points to this more complete wrapper utility.

You could also use xmllint, which is part of libxml. You may well already have it installed. Example usage:

xmllint --noout --schema XSD_FILE XML_FILE

One problem is that libxml doesn't implement all of the specification, so you may run into issues :(

Alternatively, if you are on Windows, you can use msxml, but you will need some sort of wrapper to call it, such as the GUI one described in this DDJ article. However, it seems most people on Windows use an XML Editor, such as Notepad++ (as described in Nate's answer) or XML Notepad 2007 as suggested by SteveC (there are also several commercial editors which I won't mention here).

Finally, you'll find different programs will, unfortunately, give different results. This is largely due to the complexity of the XSD spec. You may want to test your schema with several tools.

UPDATE: I've expanded on this in a blog post.