I'm not sure what the problem is. I just can't find any games or connect to them. It works between two macs. There was a similar question claiming that it does work but not stating how.
You can not play them together:
Multiplayer matches between Mac OS and Windows clients do not work as the game version is different on each operating system. This leads to a version mismatch error when attempting to join a match. The current Mac version 1.0.5 is only in sync with the 1.12 Windows version, when it needs to be in sync the Windows version 1.13.
Although that is from Age of Empires 3 I think that it's safe to assume the most recent release would be the more likely to accomodate cross platform matchups. Not to mention EVERY thread online says that you can't do it.
You could run Windows off your MAC and then play them against each other, but this would involve quite a bit of effort.