Do military aircraft overflying other countries' airspace require special clearance?
In general, a diplomatic clearance is required for overflight of military aircraft over other countries. The aircraft are considered state aircraft and prior clearance has to be obtained through diplomatic channels. Note that the clearance is usually issued by the defence ministry of the concerned country.
The mode of clearance and monitoring varies from country to country. In case of US:

Foreign governments seeking diplomatic clearance for state aircraft to transit U.S. territorial airspace or land in the United States must obtain a diplomatic clearance number (DCN) issued in advance by the Office of International Security Operations, Bureau of Political Military Affairs (PM/ISO), Department of State. The DCN authorizes the aircraft to transit or land in the United States and/or its territories, in accordance with the approved itinerary.

The overflight permissions are also dependent on agreement between various countries, like India-Pakistan. In some cases, like some EU countries, military transport aircraft can operate without diplomatic clearance.
Some other countries, like Canada give blanket clearance for military aircraft from some countries:

3.2.3 Blanket Diplomatic Clearances to Foreign Military Aircraft

By order-in-council, United States, United Kingdom, and New Zealand military aircraft are exempted from the requirement to have a formal diplomatic clearance (see 3.2.1 above) prior to overflying and/or landing in Canada.

Military aircraft from North Atlantic Treaty Organization countries other than the United States and the United Kingdom are granted clearances on an annual basis. These clearances do not apply to aircraft carrying armed soldiers, armaments and/or other dangerous goods, nor do they apply to aircraft carrying government personnel.



The procedure is usually the same in most of the countries- the overflight request is given through diplomatic channels to the countries' defence ministry, which then evaluates it and approves (or rejects it). The procedure for Canada is given here:

The state of origin will provide full flight details, as outlined in Annex A, in a diplomatic note from its embassy to Foreign Affairs and International Trade Canada (DFAIT). DFAIT will consult with the Department of National Defence (DND) Operations Centre and, if the foreign military aircraft is landing at a civilian airport, with the Foreign Inspection Division to determine whether any pre-conditions should be imposed. After this consultation, DFAIT will reply to the requesting embassy by a return diplomatic note. On advice from DFAIT, the DND Operations Centre officer will then issue the appropriate flight clearance and distribute copies to the interested parties.

In case of India:

For clearance of flights by foreign military aircraft, the concerned diplomatic mission in India or abroad are required to apply to the Ministry of External Affairs with copy to Air Headquaters/Naval Headquaters forclearance of such flights. After clearance given by Ministry of External Affairs, Air Hqrs/Naval Headquaters will issue necessary AOR number for operation of such aircraft, whether it is overflying Indian air space or landing at any Indian airport (civil or defence).

The monitoring of overflying aircraft depends on the country. Civil ATC usually monitors the aircraft carrying transponders, while the military radars (where available), monitor all air traffic and scramble fighters when the aircraft is not identified/responding properly. Overflight without permission may at the very least result in the aircraft being forced to land by authorities.