How do I build/run this simple Mahout program without getting exceptions?
You need to use the "job" JAR file provided by Mahout. It packages up all the dependencies. You need to add your classes to it too. This is how all the Mahout examples work. You shouldn't put Mahout jars in the Hadoop lib since that sort of "installs" a program too deeply in Hadoop.
if you will take code for examples from https://github.com/tdunning/MiA repository, then it contains ready to use pom.xml file for Maven. And when you compile code with mvn package, then it will create mia-0.1-job.jar in the target directory - this archive contains all dependencies, except Hadoop's, so you can run it on Hadoop cluster without problems