If your MSMQ environment has AD Integration installed, you can use PUBLIC= formatnames for public queues and PRIVATE= formatnames for private queues. PUBLIC= formatnames are pretty easy to work with: if you know the path of the queue, you can get or construct a PUBLIC= formatname, and if you have a PUBLIC= formatname, you can get the path of the queue.
PRIVATE= formatnames aren't so easy. You can't construct a PRIVATE= formatname, the way you can a PUBLIC= formatname. The syntax of the formatname is PRIVATE=qmguid\queueID. You can get the qmguid, which identifies the queue manager hosting the queue, but the queueID is a number internal to the queue manager, and the only way to get it is by extracting it from a PRIVATE= formatname. It is not exposed as a queue property.
So, if you have the path to a private queue and you want a PRIVATE= formatname, what can you do? If it's a local queue, you can pass the path to MQPathNameToFormatName and it should return a PRIVATE= formatname. If it's not a local queue, you're out of luck. I was actually bitten by this while writing a test, and the only solution I found was to write a a little program which runs on the remote machine, performs the MQPathNameToFormatName call, and saves the result somewhere where the rest of the test can get at it!
It's a little easier if you have a PRIVATE= formatname and want to get the path of the queue. Start out by calling MQGetQueueProperties with the formatname and retrieving the PROPID_Q_PATHNAME property. If it's a local queue, you're done; if not, you'll get an error back and it gets complicated. First, you have to figure out what machine the queue is on! You can extract the qmguid from the formatname and pass it to MQGetMachineProperties, retrieving the PROPID_QM_PATHNAME property, which gives you the name of the remote computer. That gives you one of the inputs required for MQMgmtGetInfo, and the other one is QUEUE=formatname. Call MQMgmtGetInfo to retrieve the PROPID_MGMT_QUEUE_PATHNAME, and if the queue is "active", you'll have the path.