1) Only units with "Militia" in their name qualify for free upkeep.

2) You get different "free upkeep slots" for different types of walls. Basic pallisade is 2, Wooden wall is 3 etc... (it's written in each wall type building card). All units over this cap have to be paid for.

3) You only get free upkeep for those Militia units that can be trained locally. Building only one town up to churn out halberd militia for you whole empire will not work - they will be free in that town, but paid in towns with lower level barracks/walls.