The decision to establish a penal colony in NSW was made some time in 1786. On 18 August 1786, Lord Sydney wrote to the Lord Commissioners of the Treasury. After outlining the reasons for the decision, he asked for ships to carry 750 convicts and for suitable equipment. On 31 August 1786, Sydney requested the Lords of the Admiralty to provide a ship of war, a tender and a force of 160 marines with the appropriate number of other ranks.
Captain Arthur Phillip appointing him Governor of the new colony. Later that month, commissions were issued to the subordinate officers necessary to the administration of the new settlement.
On 6 December. two Orders-in-Council were passed declaring the eastern coast of NSW a place to which offenders sentenced to transportation might be conveyed.
Early in 1787, the administrative arrangements for the new colony were completed. An act of Parliament was passed creating a Court of Criminal Jurisdiction in NSW, while on April 2 a more detailed Commission was granted Arthur Phillip appointing him "Captain-General and Commander-in-Chief" followed by detailed Instructions on April 29.
The difference between the two is that the Commission gave Phillip his powers, the Instructions told him how to exercise those powers. It was easier to issue a broad Commission since these could be hard to alter but then qualify it by the more easily alterable Instructions. The last piece of paper work was completed on 5 May, with the fleet sailing on May 13 1787
If you think about it, the time lapse between the decision to establish a new penal colony on the other side of the world and the departure was well under twelve months. We know that Phillip experienced a range of difficulties in getting the fleet properly kitted out, but the time period is still remarkably short. Quite remarkable, really.