Download the installation package for MapServer from

http://gisinternals.com/sdk/

and unpack the binaries.

The following structure is expected for the MXD2map converter:

ms_6.1-dev
|-- bin
|   |-- curl
|   |-- gdal
|   |   |-- apps
|   |   |-- plugins
|   |   `-- plugins-optional
|   |-- gdal-data
|   |-- ms
|   |   |-- apps
|   |   |-- java
|   |   `-- plugins
|   |       |-- mssql2008
|   |       |-- oci
|   |       `-- sde
|   `-- proj
|       |-- apps
|       `-- SHARE
`-- doc