This was written in 2004 for an old First Issues website and it will (eventually) be rewritten for FICC with better placed arrows and without the unnecessary prefix of "4" for everything.
First a general note on the Malayan / Malaysian states. When they first issued their own stamps, they often had to be used with other stamps (frequently Straits Settlements) for external postage. Today and in the previous federations, the states have continued to issue some of their own stamps (usually low value definitives and sometimes commemoratives). Periods in between can be equally confusing.
4.1 Straits Settlements, originally covered by the Indian Post Office Act, first issued its own stamps in 1867. After Japanese Occupation in 1942 and British Military Administration (BMA), the component states issued their own stamps. Malacca and Penang joined the Malay Union in 1946. Singapore used Federation stamps in addition to its own from 1958 and joined the Federation of Malaysia in 1963, but seceded in 1965 to become an independent republic within the British Commonwealth.
4.2 Of the five "Unfederated" Malay States, Johore was the first to issue its own stamps in 1876. Following Japanese occupation in 1942 and British Military Administration in 1945, it joined the Malay Union in 1946, which became the Federation of Malaya in 1948 and grew into the Federation of Malaysia in 1963. Throughout its various memberships, Johore continued to issue its own stamps at various times. Kedah. Kelantan, and Tregganu (plus Perlis, which used Kedah's stamps until 1948) followed a similar path, with the exception of being transferred to Thai occupation in 1943.
4.3 Negri Sembilan, Selangor, Pahang and Perak (plus Sungei Ujong which became part of Negri Sembilan in 1895) all issued their first stamps in the late 1800s before founding the Federated States in 1896 and the Malayan Postal Union in 1935. Following Japanese occupation and BMA, they followed the same path as the unfederated states, through the Malay Union then the two Federations. Again, they continued to issue their own stamps throughout.
4.4 Stamps for the Federated Malay States were first issued in 1900 with the component states using their own, Federation and each others' (in times of shortage) stamps until 1935 when the Malayan Postal Union was formed and the states made separate issues again.
4.5 The Malayan Postal Union issued only Postage Due stamps, at first only for the Federated States, but after WW2 for Straits Settlements and the subsequent Federation. This entity does not fit well into the diagram.
4.6 The states of Northern Borneo, North Borneo itself, Labuan (which used the stamps of North Borneo from 1946) Sarawak and Brunei all issued their own stamps in the 1800s (Scott starts Brunei in 1906 as previous issues were for local use only). The states were subject to Japanese occupation in 1942 and British Military Administration in 1945, in both cases being administered separately from the other states covered here. After BMA, the three states continued to issue their own stamps. North Borneo joined the Federation of Malaysia in 1963 and changed its name to Sabah in 1964. Sarawak joined the Federation in 1963. Brunei did not join Malaysia and became fully independent in 1985.
4.7 Japan occupied the whole of the area in WW2, administering the Northern Borneo states separately from the rest, and making individual occupation issues for Brunei, North Borneo and Sarawak.
4.8 Japan transferred Kedah. Kelantan, Tregganu and Perlis to Thai control in 1943.
4.9 Following the defeat of Japan, the area came under British Military Administration, again controlled separately.
4.10 In 1946, the four Federated states, the five "unfederated" states, plus Malacca and Penang (previously part of Straits Settlements) formed the Malay Union (no stamps issued) which in 1948 became the Federation of Malaya. the first Federation stamps were issued in 1957.
4.11 In 1963 the eleven states of the Federation plus Sabah (formerly North Borneo) and Sarawak formed the Federation of Malaysia.
4.12 Sabah, formerly North Borneo, and Sarawak joined the Federation of Malaysia in 1963.
4.13 Brunei chose to remain independent rather than joining the Federation. Resisting invasion by Indonesia with British aid, it became fully independent in 1985.
4.14 Malacca and Penang, formerly Straits Settlements, joined the Malay Union in 1946.
4.15 Singapore used Federation stamps in addition to its own from 1958 and joined the Federation of Malaysia in 1963, but seceded in 1965 to become an independent republic within the British Commonwealth.
4.16 Cocos Islands were administered through Ceylon from 1876, transferred to Straits Settlements in 1886 and incorporated into Singapore in 1903. When Singapore became independent in 1955, they were transferred to Australia, whose stamps they used until 1963 when they made their own first issue. (Australian stamps were used again temporarily when switching to decimal currency).
4.17 Christmas Island was administered under Straits Settlements from 1900 and, following Japanese occupation, by Singapore. In 1958 it was briefly a Crown Colony, then transferred to Australia and made its own firs issue.
4.18 Federal Territory Issues have been made for use in Kuala Lumpur (1979), Labuan (1984) and Putrajaya (2001).