Meaning Absent without permission.
Origin
Leave simply means permission, although that usage is now largely defunct. The earliest reference I can find to that usage in the expression 'absent without leave' comes from Mr. Rushworth's Historical Collections, Volume VI, 1646 to 1648, published 1708:
The same day the Peers call'd over their House, and order'd, That the Lords, absent without Leave, or just Excuse, be fin'd £100 a Man.
AWOL is a term originating in the US military, as an acronym for 'Absent Without Official Leave'. This is much later than 'absent without leave'. H. L. Mencken, in The American Language, 1945, records it as originating during the [American] Civil War, but without hard evidence. He states:
"[In the Confederate Army] absences of short duration were often unpunished and in other cases offenders received such trivial sentences as reprimand by a company officer, digging a stump, carrying a rail for an hour or two, wearing a placard inscribed with the letters AWOL."
As far as documentary evidence goes, the earliest I can find date from the First World War - an apt reason for absenting oneself without permission, if there ever was one. The term seems to have first been applied to American servicemen, in newspaper reports of the time. For example, this piece from The New York Times, July, 1919:
The prize "A.W. O.L." performer of the American Expeditionary Force has been discovered. He is Private Jack Engleton of Ambulance Company 1, Second Divison. Engleton has been absent without leave almost two years, having been away from his division during the entire period of its fighting activities in Europe.