I would have expected to see com.ibm.mqjms.jar in the CLASSPATH for a JMS app, not com.ibm.mq.*.
Depending on the version of WMQ you are using, please reference the Environment Variables page in the Infocenter. WMQ V6 page is here (see Table #2), and the WMQ v7 page is here (see the table and the notes below). Note that the classes have been repackaged between versions and the CLASSPATH requirements are quite different.
On UNIX flavors, you can run the setmqjms script to configure the environment for WMQ JMS. It lives in /opt/mqm/java/bin or /usr/mqm/java/bin on AIX. This assumes a standard WMQ client installation, though. If you just grabbed the jars and relocated them, it won't work. In particular, if you just grabbed the com.ibm.mq* jars it likely won't work. You can verify your installation by running the Initial Verification Test (IVT) supplied with the client install. The additional benefit of using a full WMQ client is that all of the trace utilities and sample code and other diagnostics are installed.
One other piece of advice, be sure to use the WMQ v7 client even if the WMQ server is at v6. This is because WMQ v6 is going out of service next year and will not be supported after that. Using the v7 client now will save you a migration later, CLASSPATH changes, etc. In addition, the v7 classes have lots of cool new features when used with a v7 QMgr such as automatic client reconnection to the same or different QMgr, depending on your configuration. The WMQ client install is a free download (registration required) as SupportPac MQC7.